Algorithms and Data Structures: 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 – August 2, 2017, Proceedings

Description

This book constitutes the refereed proceedings of the 15th Algorithms and Data Structures Symposium, WADS 2017, held in St. John's, NL, Canada, in July/August 2017. The 49 full papers presented together with 3 abstracts of invited talks were carefully reviewed and selected from 109 submissions. They present original research on the theory and application of algorithms and data structures in many areas, including combinatorics, computational geometry, databases, graphics, and parallel and distributed computing. The WADS Symposium, which alternates with the Scandinavian Symposium and Workshops on Algorithm Theory, SWAT, is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. Papers presenting original research on the theory and application of algorithms and data structures. Front Matter ....Pages I-XX Covering Segments with Unit Squares (Ankush Acharyya, Subhas C. Nandy, Supantha Pandit, Sasanka Roy)....Pages 1-12 Replica Placement on Bounded Treewidth Graphs (Anshul Aggarwal, Venkatesan T. Chakaravarthy, Neelima Gupta, Yogish Sabharwal, Sachin Sharma, Sonika Thakral)....Pages 13-24 Fast Exact Algorithms for Survivable Network Design with Uniform Requirements (Akanksha Agrawal, Pranabendu Misra, Fahad Panolan, Saket Saurabh)....Pages 25-36 The Complexity of Tree Partitioning (Zhao An, Qilong Feng, Iyad Kanj, Ge Xia)....Pages 37-48 Effectiveness of Local Search for Art Gallery Problems (Sayan Bandyapadhyay, Aniket Basu Roy)....Pages 49-60 Parameterized Complexity of Geometric Covering Problems Having Conflicts (Aritra Banik, Fahad Panolan, Venkatesh Raman, Vibha Sahlot, Saket Saurabh)....Pages 61-72 Obedient Plane Drawings for Disk Intersection Graphs (Bahareh Banyassady, Michael Hoffmann, Boris Klemz, Maarten Löffler, Tillmann Miltzow)....Pages 73-84 \(\delta \)-Greedy t-spanner (Gali Bar-On, Paz Carmi)....Pages 85-96 Dynamic Graph Coloring (Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen et al.)....Pages 97-108 Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron (Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Anna Lubiw)....Pages 109-120 An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width (Benjamin Bergougnoux, Mamadou Moustapha Kanté, O-Joung Kwon)....Pages 121-132 Improved Algorithms for Computing k-Sink on Dynamic Flow Path Networks (Binay Bhattacharya, Mordecai J. Golin, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh)....Pages 133-144 A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings (Therese Biedl, Philippe Demontigny)....Pages 145-156 Splitting \(B_2\)-VPG Graphs into Outer-String and Co-Comparability Graphs (Therese Biedl, Martin Derka)....Pages 157-168 A Deterministic Algorithm for Online Steiner Tree Leasing (Marcin Bienkowski, Artur Kraska, Paweł Schmidt)....Pages 169-180 The I/O Complexity of Strassen’s Matrix Multiplication with Recomputation (Gianfranco Bilardi, Lorenzo De Stefani)....Pages 181-192 Maximum Plane Trees in Multipartite Geometric Graphs (Ahmad Biniaz, Prosenjit Bose, Kimberly Crosbie, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari et al.)....Pages 193-204 Local Routing in Spanners Based on WSPDs (Prosenjit Bose, Jean-Lou De Carufel, Vida Dujmović, Frédérik Paradis)....Pages 205-216 Relaxing the Irrevocability Requirement for Online Graph Algorithms (Joan Boyar, Lene M. Favrholdt, Michal Kotrbčík, Kim S. Larsen)....Pages 217-228 Approximating Small Balanced Vertex Separators in Almost Linear Time (Sebastian Brandt, Roger Wattenhofer)....Pages 229-240 Balanced Line Separators of Unit Disk Graphs (Paz Carmi, Man Kwun Chiu, Matthew J. Katz, Matias Korman, Yoshio Okamoto, André van Renssen et al.)....Pages 241-252 All-Pairs Shortest Paths in Geometric Intersection Graphs (Timothy M. Chan, Dimitrios Skrepetos)....Pages 253-264 The Complexity of Drawing Graphs on Few Lines and Few Planes (Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff)....Pages 265-276 Modular Circulation and Applications to Traffic Management (Philip Dasler, David M. Mount)....Pages 277-288 The Homogeneous Broadcast Problem in Narrow and Wide Strips (Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak)....Pages 289-300 Minimizing the Continuous Diameter When Augmenting a Tree with a Shortcut (Jean-Lou De Carufel, Carsten Grimm, Stefan Schirra, Michiel Smid)....Pages 301-312 Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs (Erik D. Demaine, Quanquan C. Liu)....Pages 313-324 Capacitated Center Problems with Two-Sided Bounds and Outliers (Hu Ding, Lunjia Hu, Lingxiao Huang, Jian Li)....Pages 325-336 Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity (Ran Duan, Le Zhang)....Pages 337-348 Improved Distance Sensitivity Oracles via Tree Partitioning (Ran Duan, Tianyi Zhang)....Pages 349-360 Delta-Fast Tries: Local Searches in Bounded Universes with Linear Space (Marcel Ehrhardt, Wolfgang Mulzer)....Pages 361-372 Split Packing: Packing Circles into Triangles with Optimal Worst-Case Density (Sándor P. Fekete, Sebastian Morr, Christian Scheffer)....Pages 373-384 Fast and Compact Planar Embeddings (Leo Ferres, José Fuentes, Travis Gagie, Meng He, Gonzalo Navarro)....Pages 385-396 When Can Graph Hyperbolicity Be Computed in Linear Time? (Till Fluschnik, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, Nimrod Talmon)....Pages 397-408 Optimal Query Time for Encoding Range Majority (Paweł Gawrychowski, Patrick K. Nicholson)....Pages 409-420 Conditional Lower Bounds for Space/Time Tradeoffs (Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat)....Pages 421-436 Posimodular Function Optimization (Magnús M. Halldórsson, Toshimasa Ishii, Kazuhisa Makino, Kenjiro Takazawa)....Pages 437-448 How to Play Hot and Cold on a Line (Herman Haverkort, David Kübel, Elmar Langetepe, Barbara Schwarzwald)....Pages 449-460 Faster Algorithm for Truth Discovery via Range Cover (Ziyun Huang, Hu Ding, Jinhui Xu)....Pages 461-472 Searching Edges in the Overlap of Two Plane Graphs (John Iacono, Elena Khramtcova, Stefan Langerman)....Pages 473-484 Improved Average Complexity for Comparison-Based Sorting (Kazuo Iwama, Junichi Teruyama)....Pages 485-496 An EPTAS for Scheduling on Unrelated Machines of Few Different Types (Klaus Jansen, Marten Maack)....Pages 497-508 A Polynomial Kernel for Distance-Hereditary Vertex Deletion (Eun Jung Kim, O-Joung Kwon)....Pages 509-520 Busy Time Scheduling on a Bounded Number of Machines (Extended Abstract) (Frederic Koehler, Samir Khuller)....Pages 521-532 Algorithms for Covering Multiple Barriers (Shimin Li, Haitao Wang)....Pages 533-544 An Improved Algorithm for Diameter-Optimally Augmenting Paths in a Metric Space (Haitao Wang)....Pages 545-556 Covering Uncertain Points in a Tree (Haitao Wang, Jingru Zhang)....Pages 557-568 Stochastic Closest-Pair Problem and Most-Likely Nearest-Neighbor Search in Tree Spaces (Jie Xue, Yuan Li)....Pages 569-580 On the Expected Diameter, Width, and Complexity of a Stochastic Convex-Hull (Jie Xue, Yuan Li, Ravi Janardan)....Pages 581-592 Back Matter ....Pages 593-594