Algorithms and Data Structures: 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings

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