WALCOM: Algorithms and Computation: 13th International Conference, WALCOM 2019, Guwahati, India, February 27 – March 2, 2019, Proceedings (Lecture Notes in Computer Science Book 11355)

This book constitutes the proceedings of the 13th International Conference and Workshop on Algorithms and Computation, WALCOM 2019, held in Guwahati, India, in February/ March 2019. The 30 full papers presented were carefully reviewed and selected from 100 submissions. The papers are organized in topical headings on the facility location problem; computational geometry; graph drawing; graph algorithms; approximation algorithms; miscellaneous; data structures; parallel and distributed algorithms; and packing and covering. Front Matter ....Pages I-XVI Front Matter ....Pages 1-1 Graph Profile Realizations and Applications to Social Networks (Amotz Bar-Noy, Keerti Choudhary, David Peleg, Dror Rawitz)....Pages 3-14 Parameterized Computational Geometry via Decomposition Theorems (Fahad Panolan, Saket Saurabh, Meirav Zehavi)....Pages 15-27 Front Matter ....Pages 29-29 r-Gatherings on a Star (Shareef Ahmed, Shin-ichi Nakano, Md. Saidur Rahman)....Pages 31-42 Topological Stability of Kinetic k-centers (Ivor Hoog v.d., Marc van Kreveld, Wouter Meulemans, Kevin Verbeek, Jules Wulms)....Pages 43-55 A Linear Time Algorithm for the r-Gathering Problem on the Line (Extended Abstract) (Anik Sarker, Wing-kin Sung, M. Sohel Rahman)....Pages 56-66 Front Matter ....Pages 67-67 Maximum-Width Empty Square and Rectangular Annulus (Sang Won Bae, Arpita Baral, Priya Ranjan Sinha Mahapatra)....Pages 69-81 Hard and Easy Instances of L-Tromino Tilings (Javier T. Akagi, Carlos F. Gaona, Fabricio Mendoza, Manjil P. Saikia, Marcos Villagra)....Pages 82-95 The Prefix Fréchet Similarity (Christian Scheffer)....Pages 96-107 Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics (Stefan Klootwijk, Bodo Manthey, Sander K. Visser)....Pages 108-120 Optimal Partition of a Tree with Social Distance (Masahiro Okubo, Tesshu Hanaka, Hirotaka Ono)....Pages 121-132 Front Matter ....Pages 133-133 Flat-Foldability for 1 × n Maps with Square/Diagonal Grid Patterns (Yiyang Jia, Yoshihiro Kanamori, Jun Mitani)....Pages 135-147 (k, p)-Planarity: A Relaxation of Hybrid Planarity (Emilio Di Giacomo, William J. Lenhart, Giuseppe Liotta, Timothy W. Randolph, Alessandra Tappini)....Pages 148-159 Drawing Clustered Graphs on Disk Arrangements (Tamara Mchedlidze, Marcel Radermacher, Ignaz Rutter, Nina Zimbel)....Pages 160-171 Front Matter ....Pages 173-173 Computing the Metric Dimension by Decomposing Graphs into Extended Biconnected Components (Duygu Vietz, Stefan Hoffmann, Egon Wanke)....Pages 175-187 On the Algorithmic Complexity of Double Vertex-Edge Domination in Graphs (Y. B. Venkatakrishnan, H. Naresh Kumar)....Pages 188-198 The Upper Bound on the Eulerian Recurrent Lengths of Complete Graphs Obtained by an IP Solver (Shuji Jimbo, Akira Maruoka)....Pages 199-208 A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition (Takuya Tamori, Kei Kimura)....Pages 209-218 Multilevel Planarity (Lukas Barth, Guido Brückner, Paul Jungeblut, Marcel Radermacher)....Pages 219-231 Front Matter ....Pages 233-233 Weighted Upper Edge Cover: Complexity and Approximability (Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Florian Sikora)....Pages 235-247 Linear Pseudo-Polynomial Factor Algorithm for Automaton Constrained Tree Knapsack Problem (Soh Kumabe, Takanori Maehara, Ryoma Sin’ya)....Pages 248-260 Matching Sets of Line Segments (Hyeyun Yang, Antoine Vigneron)....Pages 261-273 Front Matter ....Pages 275-275 Efficient Algorithm for Box Folding (Koichi Mizunashi, Takashi Horiyama, Ryuhei Uehara)....Pages 277-288 Analyzing the Quantum Annealing Approach for Solving Linear Least Squares Problems (Ajinkya Borle, Samuel J. Lomonaco)....Pages 289-301 Front Matter ....Pages 303-303 Greedy Consensus Tree and Maximum Greedy Consensus Tree Problems (Wing-Kin Sung)....Pages 305-316 A Two Query Adaptive Bitprobe Scheme Storing Five Elements (Mirza Galib Anwarul Husain Baig, Deepanjan Kesh, Chirag Sodani)....Pages 317-328 Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index (Ali Alatabbi, Jacqueline W. Daykin, Neerja Mhaskar, M. Sohel Rahman, W. F. Smyth)....Pages 329-338 Front Matter ....Pages 339-339 Towards Work-Efficient Parallel Parameterized Algorithms (Max Bannach, Malte Skambath, Till Tantau)....Pages 341-353 Arbitrary Pattern Formation on Infinite Grid by Asynchronous Oblivious Robots (Kaustav Bose, Ranendu Adhikary, Manash Kumar Kundu, Buddhadeb Sau)....Pages 354-366 Front Matter ....Pages 367-367 Packing 2D Disks into a 3D Container (Helmut Alt, Otfried Cheong, Ji-won Park, Nadja Scharf)....Pages 369-380 Covering and Packing of Rectilinear Subdivision (Satyabrata Jana, Supantha Pandit)....Pages 381-393 Minimum Membership Covering and Hitting (Joseph S. B. Mitchell, Supantha Pandit)....Pages 394-406 Capacitated Discrete Unit Disk Cover (Pawan K. Mishra, Sangram K. Jena, Gautam K. Das, S. V. Rao)....Pages 407-418 Correction to: Weighted Upper Edge Cover: Complexity and Approximability (Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Florian Sikora)....Pages C1-C1 Back Matter ....Pages 419-420