Algorithms and Data Structures: 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings (Lecture Notes in Computer Science Book 11646)

This book constitutes the refereed proceedings of the 16th International Symposium on Algorithms and Data Structures, WADS, 2019, held in Edmonton, AB, Canada, in August 2019. The 42 full papers presented together with 3 invited lectures, we carefully reviewed and selected from a total of 88 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. Front Matter ....Pages i-xx Succinct Data Structures for Families of Interval Graphs (Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo, Srinivasa Rao Satti)....Pages 1-13 On Polynomial-Time Combinatorial Algorithms for Maximum L-Bounded Flow (Kateřina Altmanová, Petr Kolman, Jan Voborník)....Pages 14-27 Efficient Nearest-Neighbor Query and Clustering of Planar Curves (Boris Aronov, Omrit Filtser, Michael Horton, Matthew J. Katz, Khadijeh Sheikhan)....Pages 28-42 Positive-Instance Driven Dynamic Programming for Graph Searching (Max Bannach, Sebastian Berndt)....Pages 43-56 How to Morph a Tree on a Small Grid (Fidel Barrera-Cruz, Manuel Borrazzo, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani et al.)....Pages 57-70 Approximating Robust Bin Packing with Budgeted Uncertainty (Aniket Basu Roy, Marin Bougeret, Noam Goldberg, Michael Poss)....Pages 71-84 Rank-Select Indices Without Tears (Tim Baumann, Torben Hagerup)....Pages 85-98 A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs (Amariah Becker, Philip N. Klein, Aaron Schild)....Pages 99-111 A Framework for Vehicle Routing Approximation Schemes in Trees (Amariah Becker, Alice Paul)....Pages 112-125 Avoidable Vertices and Edges in Graphs (Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich, Martin Milanič, Mary Servatius)....Pages 126-139 Plane Hop Spanners for Unit Disk Graphs (Ahmad Biniaz)....Pages 140-154 On the Minimum Consistent Subset Problem (Ahmad Biniaz, Sergio Cabello, Paz Carmi, Jean-Lou De Carufel, Anil Maheshwari, Saeed Mehrabi et al.)....Pages 155-167 Parameterized Complexity of Conflict-Free Graph Coloring (Hans L. Bodlaender, Sudeshna Kolay, Astrid Pieterse)....Pages 168-180 Graph Isomorphism for \((H_1,H_2)\)-Free Graphs: An Almost Complete Dichotomy (Marthe Bonamy, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma)....Pages 181-195 Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs (Prosenjit Bose, Pilar Cano, Maria Saumell, Rodrigo I. Silveira)....Pages 196-210 Computing Maximum Independent Set on Outerstring Graphs and Their Relatives (Prosenjit Bose, Paz Carmi, Mark J. Keil, Anil Maheshwari, Saeed Mehrabi, Debajyoti Mondal et al.)....Pages 211-224 Online Bin Covering with Advice (Joan Boyar, Lene M. Favrholdt, Shahin Kamali, Kim S. Larsen)....Pages 225-238 Stackelberg Packing Games (Toni Böhnlein, Oliver Schaudt, Joachim Schauer)....Pages 239-253 FRESH: Fréchet Similarity with Hashing (Matteo Ceccarello, Anne Driemel, Francesco Silvestri)....Pages 254-268 Range Closest-Pair Search in Higher Dimensions (Timothy M. Chan, Saladi Rahul, Jie Xue)....Pages 269-282 Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles (Timothy M. Chan, Yakov Nekrich, Michiel Smid)....Pages 283-295 Kernelization of Graph Hamiltonicity: Proper H-Graphs (Steven Chaplick, Fedor V. Fomin, Petr A. Golovach, Dušan Knop, Peter Zeman)....Pages 296-310 Weighted Throughput Maximization with Calibrations (Vincent Chau, Shengzhong Feng, Minming Li, Yinling Wang, Guochuan Zhang, Yong Zhang)....Pages 311-324 Maximizing Dominance in the Plane and Its Applications (Jongmin Choi, Sergio Cabello, Hee-Kap Ahn)....Pages 325-338 Extending Upward Planar Graph Drawings (Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati)....Pages 339-352 Reconfiguring Undirected Paths (Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara et al.)....Pages 353-365 Online Circle Packing (Sándor P. Fekete, Sven von Höveling, Christian Scheffer)....Pages 366-379 Guess Free Maximization of Submodular and Linear Sums (Moran Feldman)....Pages 380-394 Efficient Second-Order Shape-Constrained Function Fitting (David Durfee, Yu Gao, Anup B. Rao, Sebastian Wild)....Pages 395-408 Dynamic Dictionary Matching in the Online Model (Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat)....Pages 409-422 Balanced Stable Marriage: How Close Is Close Enough? (Sushmita Gupta, Sanjukta Roy, Saket Saurabh, Meirav Zehavi)....Pages 423-437 Improved Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint (Chien-Chung Huang, Naonori Kakimura)....Pages 438-451 Inventory Routing Problem with Facility Location (Yang Jiao, R. Ravi)....Pages 452-465 A Linear-Time Algorithm for Radius-Optimally Augmenting Paths in a Metric Space (Christopher Johnson, Haitao Wang)....Pages 466-480 Geometric Firefighting in the Half-Plane (Sang-Sub Kim, Rolf Klein, David Kübel, Elmar Langetepe, Barbara Schwarzwald)....Pages 481-494 Most Vital Segment Barriers (Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, Frank Staals)....Pages 495-509 Splaying Preorders and Postorders (Caleb C. Levy, Robert E. Tarjan)....Pages 510-522 Wannabe Bounded Treewidth Graphs Admit a Polynomial Kernel for DFVS (Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Roohani Sharma, Meirav Zehavi)....Pages 523-537 Discrete Morse Theory for Computing Zigzag Persistence (Clément Maria, Hannah Schreiber)....Pages 538-552 Optimal Offline Dynamic 2, 3-Edge/Vertex Connectivity (Richard Peng, Bryce Sandlund, Daniel D. Sleator)....Pages 553-565 Zip Trees (Robert E. Tarjan, Caleb C. Levy, Stephen Timmel)....Pages 566-577 Improved Algorithms for the Bichromatic Two-Center Problem for Pairs of Points (Haitao Wang, Jie Xue)....Pages 578-591 Back Matter ....Pages 593-594