ISAAC 2016: The 27th International Symposium on Algorithms and Computation

December 12-14 2016, Darling Harbour, Sydney, Australia

ISAAC 2016 Accepted Papers

Shahram Ghandeharizadeh, Sandy Irani and Jenny Lam. The Subset Assignment Problem for Data Placement in Caches
Wenchang Luo, Yao Xu, Weitian Tong and Guohui Lin. Single machine scheduling with job-dependent machine deterioration
Andreas Emil Feldmann, Jochen Koenemann, Kanstantsin Pashkovich and Laura Sanita. Fast Approximation Algorithms for the Generalized Survivable Network Design Problem
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, Frederik Rye Skjoldjensen, Hjalte Wedel Vildhøj and Søren Vind. Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
Pavel Klavík, Yota Otachi and Jiri Sejnoha. On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
Christian Scheffer and Jan Vahrenhold. Approximate Shortest Distances Among Smooth Obstacles in 3D
Yutaro Yamaguchi. Shortest Disjoint ${\cal S}$-paths via Weighted Linear Matroid Parity
T-H. Hubert Chan, Zhihao Gavin Tang and Xiaowei Wu. On (1,\epsilon)-Restricted Max-Min Fair Allocation Problem
Shimin Li and Haitao Wang. Dispersing Points on Intervals
Hans L. Bodlaender, Hirotaka Ono and Yota Otachi. Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity
Sang Won Bae. $L_1$ Geodesic Farthest Neighbors in a Simple Polygon and Related Problems
Spyros Kontogiannis, Dorothea Wagner and Christos Zaroliagis. Hierarchical Time-Dependent Oracles
Di Chen and Mordecai Golin. Sink Evacuation on Trees with Dynamic Confluent Flows
Hicham El-Zein, Ian Munro and Matthew Robertson. Raising Permutations to Powers In Place
Kai Jin. Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach
Hung-I Yu, Tien-Ching Lin and D. T. Lee. The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints
Timothy Chan and Dimitrios Skrepetos. All-Pairs Shortest Paths in Unit Disk Graphs in Slightly Subquadratic Time
Mingyu Xiao and Hiroshi Nagamochi. A Linear-time Algorithm for Integral Multiterminal Flows in Trees
Duc Hoang and Ryuhei Uehara. Sliding tokens on a cactus
Dmitry Itsykson, Alexander Knop and Dmitry Sokolov. Complexity of distributions and average-case hardness
Amr Elmasry and Frank Kammer. Space-Efficient Plane-Sweep Algorithms
Sándor Fekete, Qian Li, Joseph Mitchell and Christian Scheffer. Universal Guard Problems
Udit Agarwal and Vijaya Ramachandran. Finding $k$ Simple Shortest Paths and Cycles
Christopher Martin and Mohammad Salavatipour. Approximation Algorithms for Capacitated $k$-Travelling Repairmen Problems
Hoang-Oanh Le and Van Bang Le. On the complexity of Matching Cut in graphs of fixed diameter
Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Günter Rote, André van Renssen, Marcel Roeloffzen and Birgit Vogtenhuber. Packing Short Plane Spanning Trees in Complete Geometric Graphs
Pankaj Agarwal, Jiangwei Pan and Will Victor. An Efficient Algorithm for Placing Electric Vehicle Charging Stations
Fu-Hong Liu, Hsiang-Hsuan Liu and Prudence W.H. Wong. Optimal Nonpreemptive Scheduling in a Smart Grid Model
Satoko Moriguchi, Kazuo Murota, Akihisa Tamura and Fabio Tardella. Scaling and Proximity Properties of Integrally Convex Functions
Yasushi Kawase and Kazuhisa Makino. Surrogate optimization for $p$-norms
Yasushi Kawase, Kazuhisa Makino and Kento Seimi. Optimal Composition Ordering Problems for Piecewise Linear Functions
Denis Kurz and Petra Mutzel. A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph
Yasushi Kawase, Tomomi Matsui and Atsushi Miyauchi. Additive Approximation Algorithms for Modularity Maximization
Martin Böhm, Marek Chrobak, Łukasz Jeż, Fei Li, Jiří Sgall and Pavel Veselý. Online Packet Scheduling with Bounded Delay and Lookahead
Tomasz Kociumaka, Solon Pissis and Jakub Radoszewski. Pattern Matching and Consensus Problems on Weighted Sequences and Profiles
Helmut Alt and Nadja Scharf. Approximating Smallest Containers for Packing Three-dimensional Convex Objects
Qian Li, Xiaoming Sun and Jialin Zhang. On the Optimality of Tape Merge of Two Lists with Similar Size
Mong-Jen Kao, Hai-Lun Tu and D.T. Lee. O(f) Bi-approximation for Capacitated Covering with Hard Capacities
Akanksha Agrawal, Fahad Panolan, Saket Saurabh and Meirav Zehavi. Simultaneous Feedback Edge Set: A Parameterized Perspective
Yangwei Liu, Hu Ding, Ziyun Huang and Jinhui Xu. Distributed and Robust Support Vector Machine
Sayan Bandyapadhyay and Kasturi Varadarajan. Approximate Clustering via Metric Partitioning
Therese Biedl and Saeed Mehrabi. On r-Guarding Thin Orthogonal Polygons
Sankardeep Chakraborty, Venkatesh Raman and Srinivasa Rao Satti. Biconnectivity, chain decomposition and st-numbering using O(n) bits
Arnab Ganguly, Wing-Kai Hon, Rahul Shah and Sharma V. Thankachan. Space-Time Trade-offs for the Shortest Unique Substring Problem
Akanksha Agrawal, Saket Saurabh, Roohani Sharma and Meirav Zehavi. Kernels for Deletion to Classes of Acyclic Digraphs
Eunjin Oh and Hee-Kap Ahn. Assigning Weights to Minimize the Covering Radius in the Plane
Sebastian Berndt and Maciej Liskiewicz. Hard Communication Channels for Steganography
Lijie Chen. Adaptivity vs Postselection, and Hardness Amplification in Polynomial Approximation
Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny and Sunil Shende. Search on a Line by Byzantine Robots
Nevzat Onur Domanic, Chi-Kit Lam and C. Gregory Plaxton. Bipartite Matching with Linear Edge Weights
Te-Li Wang, Chih-Kuan Yeh and Ho-Lin Chen. An Improved Tax Scheme for Selfish Routing
Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat and Riva Shalom. Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap
Marc Van Kreveld, Maarten Löffler, Lionov Wiratma and Frank Staals. A Refined Definition for Groups of Moving Entities and its Computation
Patrizio Angelini and Giordano Da Lozzo. Clustered Planarity with Pipes
Lucy Ham. A Gap Trichotomy for Boolean constraint problems: extending Schaefer's Theorem
Amirali Abdullah, Samira Daruki, Chitradeep Dutta Roy and Suresh Venkatasubramanian. Streaming Verification of Graph Properties
Michael Etscheid and Matthias Mnich. Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
Hugo Akitaya and Csaba Toth. Reconstruction of Weakly Simple Polygons from their Edges
Eunjin Oh and Hee-Kap Ahn. A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree
Faisal Abu-Khzam, Cristina Bazgan, Katrin Casel and Henning Fernau. Building Clusters with Lower-bounded Sizes
Yasushi Kawase and Atsushi Miyauchi. The Densest Subgraph Problem with a Convex/Concave Size Function