Computing and Combinatorics: 25th International Conference, COCOON 2019, Xi'an, China, July 29–31, 2019, Proceedings

Description

This book constitutes the proceedings of the 25th International Conference on Computing and Combinatorics, COCOON 2019, held in Xi’an, China, in July 2019. The 55 papers presented in this volume were carefully reviewed and selected from 124 submissions. The papers cover various topics, including algorithm design, approximation algorithm, graph theory, complexity theory, problem solving, optimization, computational biology, computational learning, communication network, logic, and game theory. Front Matter ....Pages i-xiii Fully Dynamic Arboricity Maintenance (Niranka Banerjee, Venkatesh Raman, Saket Saurabh)....Pages 1-12 A Lower Bound on the Growth Constant of Polyaboloes on the Tetrakis Lattice (Gill Barequet, Minati De)....Pages 13-24 An FPTAS for a General Class of Parametric Optimization Problems (Cristina Bazgan, Arne Herzel, Stefan Ruzika, Clemens Thielen, Daniel Vanderpooten)....Pages 25-37 Geodesic Fault-Tolerant Additive Weighted Spanners (Sukanya Bhattacharjee, R. Inkulu)....Pages 38-51 Diameter of Colorings Under Kempe Changes (Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler et al.)....Pages 52-64 Dominating Set on Overlap Graphs of Rectangles Intersecting a Line (Dibyayan Chakraborty, Sandip Das, Joydeep Mukherjee)....Pages 65-77 Minimizing the Cost of Batch Calibrations (Vincent Chau, Minming Li, Yinling Wang, Ruilong Zhang, Yingchao Zhao)....Pages 78-89 Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes (Prasad Chaugule, Nutan Limaye, Aditya Varre)....Pages 90-102 Chance-Constrained Submodular Knapsack Problem (Junjie Chen, Takanori Maehara)....Pages 103-114 Approximation Hardness of Travelling Salesman via Weighted Amplifiers (Miroslav Chlebík, Janka Chlebíková)....Pages 115-127 Deleting to Structured Trees (Pratyush Dayal, Neeldhara Misra)....Pages 128-139 Sensitivity, Affine Transforms and Quantum Communication Complexity (Krishnamoorthy Dinesh, Jayalal Sarma)....Pages 140-152 On Exactly Learning Disjunctions and DNFs Without Equivalence Queries (Ning Ding)....Pages 153-165 Interactive Physical Zero-Knowledge Proof for Norinori (Jean-Guillaume Dumas, Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki, Tatsuya Sasaki, Hideaki Sone)....Pages 166-177 On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models (Purnata Ghosal, B. V. Raghavendra Rao)....Pages 178-192 Many-to-One Popular Matchings with Two-Sided Preferences and One-Sided Ties (Kavitha Gopal, Meghana Nasre, Prajakta Nimbhorkar, T. Pradeep Reddy)....Pages 193-205 Feasibility Algorithms for the Duplication-Loss Cost (Paweł Górecki, Alexey Markin, Oliver Eulenstein)....Pages 206-218 Imbalance, Cutwidth, and the Structure of Optimal Orderings (Jan Gorzny, Jonathan F. Buss)....Pages 219-231 Smaller Universal Targets for Homomorphisms of Edge-Colored Graphs (Grzegorz Guśpiel)....Pages 232-239 A Simple Construction of Broadcast Graphs (Hovhannes A. Harutyunyan, Zhiyuan Li)....Pages 240-253 No-Bend Orthogonal Drawings and No-Bend Orthogonally Convex Drawings of Planar Graphs (Extended Abstract) (Md. Manzurul Hasan, Md. Saidur Rahman)....Pages 254-265 Branch-and-Cut Algorithms for Steiner Tree Problems with Privacy Conflicts (Alessandro Hill, Stefan Voß, Roberto Baldacci)....Pages 266-278 3D Path Network Planning: Using a Global Optimization Heuristic for Mine Water-Inrush Evacuation (Yi Hong, Deying Li, Qiang Wu, Hua Xu)....Pages 279-290 Max-Min 3-Dispersion Problems (Takashi Horiyama, Shin-ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara et al.)....Pages 291-300 Matching Cut in Graphs with Large Minimum Degree (Sun-Yuan Hsieh, Hoang-Oanh Le, Van Bang Le, Sheng-Lung Peng)....Pages 301-312 Incremental Optimization of Independent Sets Under the Reconfiguration Framework (Takehiro Ito, Haruka Mizuta, Naomi Nishimura, Akira Suzuki)....Pages 313-324 Deconstructing Parameterized Hardness of Fair Vertex Deletion Problems (Ashwin Jacob, Venkatesh Raman, Vibha Sahlot)....Pages 325-337 On 1-Factorizations of Bipartite Kneser Graphs (Kai Jin)....Pages 338-349 An Optimal Algorithm for 2-Bounded Delay Buffer Management with Lookahead (Koji M. Kobayashi)....Pages 350-362 Reoptimization of Path Vertex Cover Problem (Mehul Kumar, Amit Kumar, C. Pandu Rangan)....Pages 363-374 A Simple Local Search Gives a PTAS for the Feedback Vertex Set Problem in Minor-Free Graphs (Hung Le, Baigong Zheng)....Pages 375-386 The Seeding Algorithm for Functional k-Means Problem (Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang)....Pages 387-396 More Efficient Algorithms for Stochastic Diameter and Some Unapproximated Problems in Metric Space (Daogao Liu)....Pages 397-411 Lower Bounds for Small Ramsey Numbers on Hypergraphs (S. Cliff Liu)....Pages 412-424 APTER: Aggregated Prognosis Through Exponential Re-weighting (Yang Liu, Kristiaan Pelckmans)....Pages 425-436 An Erdős–Pósa Theorem on Neighborhoods and Domination Number (Jayakrishnan Madathil, Pranabendu Misra, Saket Saurabh)....Pages 437-444 On the Hardness of Reachability Reduction (Dongjing Miao, Zhipeng Cai)....Pages 445-455 Give and Take: Adaptive Balanced Allocation for Peer Assessments (Hideaki Ohashi, Yasuhito Asano, Toshiyuki Shimizu, Masatoshi Yoshikawa)....Pages 456-468 LIKE Patterns and Complexity (Holger Petersen)....Pages 469-477 Data Structures for Incremental Interval Coloring (J. Girish Raguvir, Manas Jyoti Kashyop, N. S. Narayanaswamy)....Pages 478-489 Lower Bounds for the Happy Coloring Problems (Ivan Bliznets, Danil Sagunov)....Pages 490-502 An Efficient Decision Procedure for Propositional Projection Temporal Logic (Xinfeng Shu, Nan Zhang)....Pages 503-515 On the Relationship Between Energy Complexity and Other Boolean Function Measures (Xiaoming Sun, Yuan Sun, Kewen Wu, Zhiyu Xia)....Pages 516-528 The One-Round Multi-player Discrete Voronoi Game on Grids and Trees (Xiaoming Sun, Yuan Sun, Zhiyu Xia, Jialin Zhang)....Pages 529-540 Competitive Auctions and Envy-Freeness for Group of Agents (Taiki Todo, Atsushi Iwasaki, Makoto Yokoo)....Pages 541-553 Upper and Lower Bounds on Approximating Weighted Mixed Domination (Mingyu Xiao)....Pages 554-566 Parameterized Algorithms for the Traveling Purchaser Problem with Additional Constraints (Mingyu Xiao, Jianan Zhang, Weibo Lin)....Pages 567-579 An Approximation Algorithm for Sorting by Bounded Singleton Moves (Shengjun Xie, Haodi Feng, Haitao Jiang, Junfeng Luan, Daming Zhu)....Pages 580-590 Universal Facility Location in Generalized Metric Space (Yicheng Xu, Dachuan Xu, Yong Zhang, Juan Zou)....Pages 591-602 Activation Probability Maximization for Target Users Under Influence Decay Model (Ruidong Yan, Yi Li, Deying Li, Yuqing Zhu, Yongcai Wang, Hongwei Du)....Pages 603-614 Maximization of Constrained Non-submodular Functions (Ruiqi Yang, Dachuan Xu, Donglei Du, Yicheng Xu, Xihong Yan)....Pages 615-626 Truthful Mechanism Design of Reversed Auction on Cloud Computing (Deshi Ye, Feng Xie, Guochuan Zhang)....Pages 627-638 Distance Constrained Vehicle Routing Problem to Minimize the Total Cost (Wei Yu, Zhaohui Liu, Xiaoguang Bao)....Pages 639-650 Greedy Algorithm for Maximization of Non-submodular Functions Subject to Knapsack Constraint (Zhenning Zhang, Bin Liu, Yishui Wang, Dachuan Xu, Dongmei Zhang)....Pages 651-662 A Proof System for a Unified Temporal Logic (Liang Zhao, Xiaobing Wang, Xinfeng Shu, Nan Zhang)....Pages 663-676 Back Matter ....Pages 677-678