Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II (Lecture Notes in Computer Science Book 10628)

The two-volume set LNCS 10627 and 10628 constitutes the refereed proceedings of the 11th International Conference on Combinatorial Optimization and Applications, COCOA 2017, held in Shanghai, China, in December 2017. The 59 full papers and 19 short papers presented were carefully reviewed and selected from 145 submissions. The papers cover most aspects of theoretical computer science and combinatorics related to computing, including classic combinatorial optimization, geometric optimization, complexity and data structures, and graph theory. They are organized in topical sections on network, approximation algorithm and graph theory, combinatorial optimization, game theory, and applications. Front Matter ....Pages I-XVIII Front Matter ....Pages 1-1 Algorithms for the Ring Star Problem (Xujin Chen, Xiaodong Hu, Zhongzheng Tang, Chenhao Wang, Ying Zhang)....Pages 3-16 Price Fluctuation in Online Leasing (Björn Feldkord, Christine Markarian, Friedhelm Meyer Auf der Heide)....Pages 17-31 Novel Scheduling for Energy Management in Microgrid (Zaixin Lu, Jd Youngs, Zhi Chen, Miao Pan)....Pages 32-44 Improved Methods for Computing Distances Between Unordered Trees Using Integer Programming (Eunpyeong Hong, Yasuaki Kobayashi, Akihiro Yamamoto)....Pages 45-60 Touring Convex Polygons in Polygonal Domain Fences (Arash Ahadi, Amirhossein Mozafari, Alireza Zarei)....Pages 61-75 On Interdependent Failure Resilient Multi-path Routing in Smart Grid Communication Network (Zishen Yang, Donghyun Kim, Wei Wang)....Pages 76-93 An Improved Branching Algorithm for (n, 3)-MaxSAT Based on Refined Observations (Wenjun Li, Chao Xu, Jianxin Wang, Yongjie Yang)....Pages 94-108 Faster Algorithms for 1-Mappability of a Sequence (Mai Alzamel, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis, Jakub Radoszewski, Wing-Kin Sung)....Pages 109-121 Lexico-Minimum Replica Placement in Multitrees (K. Alex Mills, R. Chandrasekaran, Neeraj Mittal)....Pages 122-137 Graph Editing to a Given Neighbourhood Degree List is Fixed-Parameter Tractable (Naomi Nishimura, Vijay Subramanya)....Pages 138-153 A New Graph Parameter to Measure Linearity (Pierre Charbit, Michel Habib, Lalla Mouatadid, Reza Naserasr)....Pages 154-168 Listing Acyclic Subgraphs and Subgraphs of Bounded Girth in Directed Graphs (Alessio Conte, Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno)....Pages 169-181 Toward Energy-Efficient and Robust Clustering Algorithm on Mobile Ad Hoc Sensor Networks (Huamei Qi, Tailong Xiao, Anfeng Liu, Su Jiang)....Pages 182-195 Front Matter ....Pages 197-197 The Cop Number of the One-Cop-Moves Game on Planar Graphs (Ziyuan Gao, Boting Yang)....Pages 199-213 The Price of Anarchy in Two-Stage Scheduling Games (Deshi Ye, Lin Chen, Guochuan Zhang)....Pages 214-225 Selfish Jobs with Favorite Machines: Price of Anarchy vs. Strong Price of Anarchy (Cong Chen, Paolo Penna, Yinfeng Xu)....Pages 226-240 An Improved Mechanism for Selfish Bin Packing (Xin Chen, Qingqin Nong, Qizhi Fang)....Pages 241-257 Front Matter ....Pages 259-259 Hamiltonian Cycles in Covering Graphs of Trees (Pavol Hell, Hiroshi Nishiyama, Ladislav Stacho)....Pages 261-275 On k-Strong Conflict–Free Multicoloring (Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro)....Pages 276-290 Tropical Paths in Vertex-Colored Graphs (Johanne Cohen, Giuseppe F. Italiano, Yannis Manoussakis, Kim Thang Nguyen, Hong Phong Pham)....Pages 291-305 The Spectral Radius and Domination Number of Uniform Hypergraphs (Liying Kang, Wei Zhang, Erfang Shan)....Pages 306-316 Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals (Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W. H. Wong, Shmuel Zaks)....Pages 317-332 Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach (Eric Angel, Nguyen Kim Thang, Shikha Singh)....Pages 333-347 Parameterized Approximation Algorithms for Some Location Problems in Graphs (Arne Leitert, Feodor F. Dragan)....Pages 348-361 Approximation Algorithms for Maximum Coverage with Group Budget Constraints (Longkun Guo, Min Li, Dachuan Xu)....Pages 362-376 Front Matter ....Pages 377-377 A Simple Greedy Algorithm for the Profit-Aware Social Team Formation Problem (Shengxin Liu, Chung Keung Poon)....Pages 379-393 Doctor Rostering in Compliance with the New UK Junior Doctor Contract (Anna Lavygina, Kris Welsh, Alan Crispin)....Pages 394-408 Bounds for Static Black-Peg AB Mastermind (Christian Glazik, Gerold Jäger, Jan Schiemann, Anand Srivastav)....Pages 409-424 Classification Statistics in RFID Systems (Zhenzao Wen, Jiapeng Huang, Linghe Kong, Min-You Wu, Guihai Chen)....Pages 425-440 On the Complexity of Robust Stable Marriage (Begum Genc, Mohamed Siala, Gilles Simonin, Barry O’Sullivan)....Pages 441-448 The Euclidean Vehicle Routing Problem with Multiple Depots and Time Windows (Liang Song, Hejiao Huang)....Pages 449-456 Online Algorithms for Non-preemptive Speed Scaling on Power-Heterogeneous Processors (Aeshah Alsughayyir, Thomas Erlebach)....Pages 457-465 An Efficient Algorithm for Judicious Partition of Hypergraphs (Tunzi Tan, Jihong Gui, Sainan Wang, Suixiang Gao, Wenguo Yang)....Pages 466-474 On Structural Parameterizations of the Matching Cut Problem (N. R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare)....Pages 475-482 Longest Previous Non-overlapping Factors Table Computation (Supaporn Chairungsee, Maxime Crochemore)....Pages 483-491 Modeling and Verifying Multi-core Programs (Nan Zhang, Zhenhua Duan, Cong Tian, Hongwei Du, Kai Yang)....Pages 492-500 Planar Vertex-Disjoint Cycle Packing: New Structures and Improved Kernel (Qilong Feng, Xiaolu Liao, Jianxin Wang)....Pages 501-508 On the Linearization of Scaffolds Sharing Repeated Contigs (Mathias Weller, Annie Chateau, Rodolphe Giroudeau)....Pages 509-517 A Memetic Algorithm for the Linear Ordering Problem with Cumulative Costs (Taoqing Zhou, Zhipeng Lü, Tao Ye, Kan Zhou)....Pages 518-526 Back Matter ....Pages 527-529