Algorithms and Complexity: 11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019, Proceedings

Description

This book constitutes the refereed conference proceedings of the 11th International Conference on Algorithms and Complexity, CIAC 2019, held in Rome, Italy, in May 2019. The 30 full papers were carefully reviewed and selected from 95 submissions. The International Conference on Algorithms and Complexity is intended to provide a forum for researchers working in all aspects of computational complexity and the use, design, analysis and experimentation of efficient algorithms and data structures. The papers present original research in the theory and applications of algorithms and computational complexity. Front Matter ....Pages i-xiii Quadratic Vertex Kernel for Split Vertex Deletion (Akanksha Agrawal, Sushmita Gupta, Pallavi Jain, R. Krithika)....Pages 1-12 The Temporal Explorer Who Returns to the Base (Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis)....Pages 13-24 Minimum Convex Partition of Point Sets (Allan S. Barboza, Cid C. de Souza, Pedro J. de Rezende)....Pages 25-37 Parameterized Complexity of Safe Set (Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi)....Pages 38-49 Parameterized Complexity of Diameter (Matthias Bentert, André Nichterlein)....Pages 50-61 Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints (René van Bevern, Oxana Yu. Tsidulko, Philipp Zschoche)....Pages 62-74 Project Games (Vittorio Bilò, Laurent Gourvès, Jérôme Monnot)....Pages 75-86 Subgraph Isomorphism on Graph Classes that Exclude a Substructure (Hans L. Bodlaender, Tesshu Hanaka, Yoshio Okamoto, Yota Otachi, Tom C. van der Zanden)....Pages 87-98 Your Rugby Mates Don’t Need to Know Your Colleagues: Triadic Closure with Edge Colors (Laurent Bulteau, Niels Grüttemeier, Christian Komusiewicz, Manuel Sorge)....Pages 99-111 \(k\)-cuts on a Path (Xing Shi Cai, Luc Devroye, Cecilia Holmgren, Fiona Skerman)....Pages 112-123 Extension of Vertex Cover and Independent Set in Some Classes of Graphs (Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikoalei, Jérôme Monnot, Florian Sikora)....Pages 124-136 On Hedonic Games with Common Ranking Property (Bugra Caskurlu, Fatih Erdem Kizilkaya)....Pages 137-148 Complexity of Scheduling for DARP with Soft Ride Times (Janka Chlebíková, Clément Dallard, Niklas Paulsen)....Pages 149-160 Vertex Deletion on Split Graphs: Beyond 4-Hitting Set (Pratibha Choudhary, Pallavi Jain, R. Krithika, Vibha Sahlot)....Pages 161-173 Fair Hitting Sequence Problem: Scheduling Activities with Varied Frequency Requirements (Serafino Cicerone, Gabriele Di Stefano, Leszek Gasieniec, Tomasz Jurdzinski, Alfredo Navarra, Tomasz Radzik et al.)....Pages 174-186 Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability (Extended Abstract) (Miguel Coviello Gonzalez, Marek Chrobak)....Pages 187-198 Searching by Heterogeneous Agents (Dariusz Dereniowski, Łukasz Kuszner, Robert Ostrowski)....Pages 199-211 Finding a Mediocre Player (Adrian Dumitrescu)....Pages 212-223 Covering Tours and Cycle Covers with Turn Costs: Hardness and Approximation (Sándor P. Fekete, Dominik Krupke)....Pages 224-236 The Parameterized Position Heap of a Trie (Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda)....Pages 237-248 Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set (Alexander Göke, Dániel Marx, Matthias Mnich)....Pages 249-261 Shortest Reconfiguration Sequence for Sliding Tokens on Spiders (Duc A. Hoang, Amanj Khorramian, Ryuhei Uehara)....Pages 262-273 Turing Tumble Is P(SPACE)-Complete (Matthew P. Johnson)....Pages 274-285 Linear-Time In-Place DFS and BFS on the Word RAM (Frank Kammer, Andrej Sajenko)....Pages 286-298 A Faster Algorithm for the Strongly Stable b-Matching Problem (Adam Kunysz)....Pages 299-310 Eternal Domination in Grids (Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes)....Pages 311-322 On the Necessary Memory to Compute the Plurality in Multi-agent Systems (Emanuele Natale, Iliad Ramezani)....Pages 323-338 Complexity of Vertex Switching on Edge-Bicolored Graphs (Ho Lam Pang, Leizhen Cai)....Pages 339-351 Independent Lazy Better-Response Dynamics on Network Games (Paolo Penna, Laurent Viennot)....Pages 352-364 Subset Feedback Vertex Set in Chordal and Split Graphs (Geevarghese Philip, Varun Rajan, Saket Saurabh, Prafullkumar Tale)....Pages 365-376 Back Matter ....Pages 377-378