Computing and Combinatorics

Description

This book constitutes the proceedings of the 24th International Conference on Computing and Combinatorics, COCOON 2018, held in Qing Dao, China, in July 2018. The 62 papers presented in this volume were carefully reviewed and selected from 120 submissions. They deal with the areas of algorithms, theory of computation, computational complexity, and combinatorics related to computing. Front Matter ....Pages I-XIX Constructing Independent Spanning Trees on Bubble-Sort Networks (Shih-Shun Kao, Jou-Ming Chang, Kung-Jui Pai, Ro-Yu Wu)....Pages 1-13 Exact Algorithms for Finding Partial Edge-Disjoint Paths (Yunyun Deng, Longkun Guo, Peihuang Huang)....Pages 14-25 A Randomized FPT Approximation Algorithm for Maximum Alternating-Cycle Decomposition with Applications (Haitao Jiang, Lianrong Pu, Letu Qingge, David Sankoff, Binhai Zhu)....Pages 26-38 Contextual Dependent Click Bandit Algorithm for Web Recommendation (Weiwen Liu, Shuai Li, Shengyu Zhang)....Pages 39-50 LP-Based Pivoting Algorithm for Higher-Order Correlation Clustering (Takuro Fukunaga)....Pages 51-62 Approximation Algorithms for a Two-Phase Knapsack Problem (Kameng Nip, Zhenbo Wang)....Pages 63-75 More Routes for Evacuation (Katsuhisa Yamanaka, Yasuko Matsui, Shin-ichi Nakano)....Pages 76-83 Fine-Grained Parameterized Complexity Analysis of Knot-Free Vertex Deletion – A Deadlock Resolution Graph Problem (Alan Diêgo Aurélio Carneiro, Fábio Protti, Uéverton S. Souza)....Pages 84-95 Approximating Global Optimum for Probabilistic Truth Discovery (Shi Li, Jinhui Xu, Minwei Ye)....Pages 96-107 Online Interval Scheduling to Maximize Total Satisfaction (Koji M. Kobayashi)....Pages 108-119 Properties of Minimal-Perimeter Polyominoes (Gill Barequet, Gil Ben-Shachar)....Pages 120-129 Computing Convex-Straight-Skeleton Voronoi Diagrams for Segments and Convex Polygons (Gill Barequet, Minati De, Michael T. Goodrich)....Pages 130-142 Polygon Queries for Convex Hulls of Points (Eunjin Oh, Hee-Kap Ahn)....Pages 143-155 Synergistic Solutions for Merging and Computing Planar Convex Hulls (Jérémy Barbay, Carlos Ochoa)....Pages 156-167 Cophenetic Distances: A Near-Linear Time Algorithmic Framework (Paweł Górecki, Alexey Markin, Oliver Eulenstein)....Pages 168-179 Computing Coverage Kernels Under Restricted Settings (Jérémy Barbay, Pablo Pérez-Lantero, Javiel Rojas-Ledesma)....Pages 180-191 Weak Mitoticity of Bounded Disjunctive and Conjunctive Truth-Table Autoreducible Sets (Liyu Zhang, Mahmoud Quweider, Hansheng Lei, Fitra Khan)....Pages 192-204 Approximation Algorithms for Two-Machine Flow-Shop Scheduling with a Conflict Graph (Yinhui Cai, Guangting Chen, Yong Chen, Randy Goebel, Guohui Lin, Longcheng Liu et al.)....Pages 205-217 On Contact Representations of Directed Planar Graphs (Chun-Hsiang Chan, Hsu-Chun Yen)....Pages 218-229 Computation and Growth of Road Network Dimensions (Johannes Blum, Sabine Storandt)....Pages 230-241 Car-Sharing Between Two Locations: Online Scheduling with Flexible Advance Bookings (Kelin Luo, Thomas Erlebach, Yinfeng Xu)....Pages 242-254 Directed Path-Width and Directed Tree-Width of Directed Co-graphs (Frank Gurski, Carolin Rehs)....Pages 255-267 Generalized Graph k-Coloring Games (Raffaello Carosi, Gianpiero Monaco)....Pages 268-279 On Colorful Bin Packing Games (Vittorio Bilò, Francesco Cellinese, Giovanna Melideo, Gianpiero Monaco)....Pages 280-292 Nonbipartite Dulmage-Mendelsohn Decomposition for Berge Duality (Nanao Kita)....Pages 293-304 The Path Set Packing Problem (Chenyang Xu, Guochuan Zhang)....Pages 305-315 Manipulation Strategies for the Rank-Maximal Matching Problem (Pratik Ghosal, Katarzyna Paluch)....Pages 316-327 Finding Maximal Common Subgraphs via Time-Space Efficient Reverse Search (Alessio Conte, Roberto Grossi, Andrea Marino, Luca Versari)....Pages 328-340 An FPT Algorithm for Contraction to Cactus (R. Krithika, Pranabendu Misra, Prafullkumar Tale)....Pages 341-352 An Approximation Framework for Bounded Facility Location Problems (Wenchang Luo, Bing Su, Yao Xu, Guohui Lin)....Pages 353-364 Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect (Jean Cardinal, Erik D. Demaine, David Eppstein, Robert A. Hearn, Andrew Winslow)....Pages 365-377 Solving the Gene Duplication Feasibility Problem in Linear Time (Alexey Markin, Venkata Sai Krishna Teja Vadali, Oliver Eulenstein)....Pages 378-390 An Efficiently Recognisable Subset of Hypergraphic Sequences (Syed M. Meesum)....Pages 391-402 Partial Homology Relations - Satisfiability in Terms of Di-Cographs (Nikolai Nøjgaard, Nadia El-Mabrouk, Daniel Merkle, Nicolas Wieseke, Marc Hellmuth)....Pages 403-415 Improved Algorithm for Finding the Minimum Cost of Storing and Regenerating Datasets in Multiple Clouds (Yingying Wang, Kun Cheng, Zimao Li)....Pages 416-427 Reconfiguring Spanning and Induced Subgraphs (Tesshu Hanaka, Takehiro Ito, Haruka Mizuta, Benjamin Moore, Naomi Nishimura, Vijay Subramanya et al.)....Pages 428-440 Generalizing the Hypergraph Laplacian via a Diffusion Process with Mediators (T.-H. Hubert Chan, Zhibin Liang)....Pages 441-453 Efficient Enumeration of Bipartite Subgraphs in Graphs (Kunihiro Wasa, Takeaki Uno)....Pages 454-466 Bipartite Graphs of Small Readability (Rayan Chikhi, Vladan Jovičić, Stefan Kratsch, Paul Medvedev, Martin Milanič, Sofya Raskhodnikova et al.)....Pages 467-479 Maximum Colorful Cliques in Vertex-Colored Graphs (Giuseppe F. Italiano, Yannis Manoussakis, Nguyen Kim Thang, Hong Phong Pham)....Pages 480-491 Partial Sublinear Time Approximation and Inapproximation for Maximum Coverage (Bin Fu)....Pages 492-503 Characterizing Star-PCGs (Mingyu Xiao, Hiroshi Nagamochi)....Pages 504-515 Liar’s Dominating Set in Unit Disk Graphs (Ramesh K. Jallu, Sangram K. Jena, Gautam K. Das)....Pages 516-528 Minimum Spanning Tree of Line Segments (Sanjana Dey, Ramesh K. Jallu, Subhas C. Nandy)....Pages 529-541 Improved Learning of k-Parities (Arnab Bhattacharyya, Ameet Gadekar, Ninad Rajgopal)....Pages 542-553 On a Fixed Haplotype Variant of the Minimum Error Correction Problem (Axel Goblet, Steven Kelk, Matúš Mihalák, Georgios Stamoulis)....Pages 554-566 Non-monochromatic and Conflict-Free Coloring on Tree Spaces and Planar Network Spaces (Boris Aronov, Mark de Berg, Aleksandar Markovic, Gerhard Woeginger)....Pages 567-578 Amplitude Amplification for Operator Identification and Randomized Classes (Debajyoti Bera)....Pages 579-591 Reconstruction of Boolean Formulas in Conjunctive Normal Form (Evgeny Dantsin, Alexander Wolpert)....Pages 592-601 A Faster FPTAS for the Subset-Sums Ratio Problem (Nikolaos Melissinos, Aris Pagourtzis)....Pages 602-614 A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time (Paniz Abedin, Arnab Ganguly, Wing-Kai Hon, Yakov Nekrich, Kunihiko Sadakane, Rahul Shah et al.)....Pages 615-625 Non-determinism Reduces Construction Time in Active Self-assembly Using an Insertion Primitive (Benjamin Hescott, Caleb Malchik, Andrew Winslow)....Pages 626-637 Minimum Membership Hitting Sets of Axis Parallel Segments (N. S. Narayanaswamy, S. M. Dhannya, C. Ramya)....Pages 638-649 Minimum Transactions Problem (Niranka Banerjee, Varunkumar Jayapaul, Srinivasa Rao Satti)....Pages 650-661 Heuristic Algorithms for the Min-Max Edge 2-Coloring Problem (Radu Stefan Mincu, Alexandru Popa)....Pages 662-674 Geometric Spanners in the MapReduce Model (Sepideh Aghamolaei, Fatemeh Baharifard, Mohammad Ghodsi)....Pages 675-687 SDP Primal-Dual Approximation Algorithms for Directed Hypergraph Expansion and Sparsest Cut with Product Demands (T.-H. Hubert Chan, Bintao Sun)....Pages 688-700 Lower Bounds for Special Cases of Syntactic Multilinear ABPs (C. Ramya, B. V. Raghavendra Rao)....Pages 701-712 Approximation Algorithms on Multiple Two-Stage Flowshops (Guangwei Wu, Jianer Chen)....Pages 713-725 Constant Factor Approximation Algorithm for l-Pseudoforest Deletion Problem (Mugang Lin, Bin Fu, Qilong Feng)....Pages 726-737 New Bounds for Energy Complexity of Boolean Functions (Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma)....Pages 738-750 Hitting and Covering Partially (Akanksha Agrawal, Pratibha Choudhary, Pallavi Jain, Lawqueen Kanesh, Vibha Sahlot, Saket Saurabh)....Pages 751-763 Back Matter ....Pages 765-767