Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II

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