Combinatorial Algorithms: 29th International Workshop, IWOCA 2018, Singapore, July 16–19, 2018, Proceedings

Description

This book constitutes the refereed post-conference proceedings of the 28th International Workshopon Combinatorial Algorithms, IWOCA 2017, held in Newcastle, NSW, Australia, in July 2017.The 30 regular papers presented in this volume together with 5 invited talks were carefully reviewed and selected from 55 submissions. They were organized in topical sessions named: approximation algorithms and hardness; computational complexity; computational geometry; graphs and combinatorics; graph colourings, labellings and power domination; heuristics; mixed integer programming; polynomial algorithms; privacy; and string algorithms. Front Matter ....Pages I-XIX Collision-Free Routing Problem with Restricted L-Path (Jammigumpula Ajay, Sasanka Roy)....Pages 1-13 Linear Clique-Width of Bi-complement Reducible Graphs (Bogdan Alecu, Vadim Lozin, Viktor Zamaraev)....Pages 14-25 Linear Ramsey Numbers (Aistis Atminas, Vadim Lozin, Viktor Zamaraev)....Pages 26-38 Graphs that Are Not Pairwise Compatible: A New Proof Technique (Extended Abstract) (Pierluigi Baiocchi, Tiziana Calamoneri, Angelo Monti, Rossella Petreschi)....Pages 39-51 Efficient Unbounded Fault-Tolerant Aggregate Signatures Using Nested Cover-Free Families (Thais Bardini Idalino, Lucia Moura)....Pages 52-64 Minimum Polygons for Fixed Visibility VC-Dimension (Moritz Beck, Sabine Storandt)....Pages 65-77 Minsum k-Sink Problem on Dynamic Flow Path Networks (Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh)....Pages 78-89 Fully Leafed Induced Subtrees (Alexandre Blondin Massé, Julien de Carufel, Alain Goupil, Mélodie Lapointe, Émile Nadeau, Élise Vandomme)....Pages 90-101 Pattern Matching for k-Track Permutations (Laurent Bulteau, Romeo Rizzi, Stéphane Vialette)....Pages 102-114 Approximation Algorithms for the p-Hub Center Routing Problem in Parameterized Metric Graphs (Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing)....Pages 115-127 On the Area Requirements of Straight-Line Orthogonal Drawings of Ternary Trees (Barbara Covella, Fabrizio Frati, Maurizio Patrignani)....Pages 128-140 A Fixed-Parameter Algorithm for the Max-Cut Problem on Embedded 1-Planar Graphs (Christine Dahn, Nils M. Kriege, Petra Mutzel)....Pages 141-152 Covering with Clubs: Complexity and Approximability (Riccardo Dondi, Giancarlo Mauri, Florian Sikora, Italo Zoppis)....Pages 153-164 On the Expected Number of Distinct Gapped Palindromic Factors (Philippe Duchon, Cyril Nicaud)....Pages 165-176 Computational Complexity of Robot Arm Simulation Problems (Tianfeng Feng, Takashi Horiyama, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Takeaki Uno et al.)....Pages 177-188 Evaluation of Tie-Breaking and Parameter Ordering for the IPO Family of Algorithms Used in Covering Array Generation (Kristoffer Kleine, Ilias Kotsireas, Dimitris E. Simos)....Pages 189-200 Efficient Enumeration of Subgraphs and Induced Subgraphs with Bounded Girth (Kazuhiro Kurita, Kunihiro Wasa, Alessio Conte, Takeaki Uno, Hiroki Arimura)....Pages 201-213 An Optimal Algorithm for Online Prize-Collecting Node-Weighted Steiner Forest (Christine Markarian)....Pages 214-223 Median of 3 Permutations, 3-Cycles and 3-Hitting Set Problem (Robin Milosz, Sylvie Hamel, Adeline Pierrot)....Pages 224-236 On the Parameterized Complexity of Colorful Components and Related Problems (Neeldhara Misra)....Pages 237-249 Analysis of Information Leakage Due to Operative Errors in Card-Based Protocols (Takaaki Mizuki, Yuichi Komano)....Pages 250-262 Zero-Suppression and Computation Models (Hiroki Morizumi)....Pages 263-272 The Crossing Number of Seq-Shellable Drawings of Complete Graphs (Petra Mutzel, Lutz Oettershagen)....Pages 273-284 Cryptographic Limitations on Polynomial-Time a Posteriori Query Learning (Mikito Nanashima)....Pages 285-297 Placing Segments on Parallel Arcs (Yen Kaow Ng, Wenlong Jia, Shuai Cheng Li)....Pages 298-310 Branch-and-Bound Algorithm for Symmetric Travelling Salesman Problem (Alexey Nikolaev, Mikhail Batsyn)....Pages 311-322 LZ-ABT: A Practical Algorithm for \(\alpha \)-Balanced Grammar Compression (Tatsuya Ohno, Keisuke Goto, Yoshimasa Takabatake, Tomohiro I, Hiroshi Sakamoto)....Pages 323-335 Faster Coreset Construction for Projective Clustering via Low-Rank Approximation (Rameshwar Pratap, Sandeep Sen)....Pages 336-348 Separating Interaction Effects Using Locating and Detecting Arrays (Stephen A. Seidel, Kaushik Sarkar, Charles J. Colbourn, Violet R. Syrotiuk)....Pages 349-360 An Efficient Representation of Partitions of Integers (Kentaro Sumigawa, Kunihiko Sadakane)....Pages 361-373 How Far From a Worst Solution a Random Solution of a \(k\,\)CSP Instance Can Be? (Jean-François Culus, Sophie Toulouse)....Pages 374-386 Back Matter ....Pages 387-388