Conference Program Detailed Booklet

Session 1 Game Theory, Chair: Thomas Erlebach (100 Minutes 5 Papers)

1. An Improved Mechanism for Selfish Bin Packing
   Xin Chen, Qingqin Nong and Qizhi Fang
2. Cost-Sharing Mechanisms for Selfish Bin Packing
   Chenhao Zhang and Guochuan Zhang
3. The Eigen-Distribution of Weighted Game Trees
   Shohei Okisaka, Weiguang Peng, Wenjuan Li and Kazuyuki Tanaka
4. The Price of Anarchy in Two-Stage Scheduling Games
   Deshi Ye, Lin Chen and Guochuan Zhang
5. Selfish Jobs with Favorite Machines: Price of Anarchy vs Strong Price of Anarchy
   Cong Chen, Paolo Penna and Yinfeng Xu

Session 2 Graph Theory, Chair: Xiao Zhou (100 Minutes 5 Papers)

1. Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals
   Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W.H. Wong and Shmuel Zaks
2. Listing Acyclic Subgraphs and Subgraphs of Bounded Girth in Directed Graphs
   Alessio Conte, Kurita Kazuhiro, Kunihiro Wasa and Takeaki Uno
3. The Cop Number of the One-Cop-Moves Game on Planar Graphs
   Ziyuan Gao and Boting Yang
4. The Spectral Radius and Domination Number of Uniform Hypergraphs
   Liying Kang, Wei Zhang and Erfang Shan
5. The 2-Median Problem on Cactus Graphs with Positive and Negative Weights
   Bai Chunsong and Kang Liying

Session 3 Combinatorial Optimization, Chair: Guochuan Zhang (100 Minutes 5 Papers)

1. Generalized pyramidal tours for the Generalized Traveling Salesman Problem
   Michael Khachay and Katherine Neznakhina
2. Improved Branching Algorithm for \((n,3)\)-MaxSAT Based on Refined Observations
   Wenjun Li, Jianxin Wang, Chao Xu and Yongjie Yang
3. New Insights for Power Edge Set Problem
   Benoit Darties, Annie Chateau, Rodolphe Giroudeau and Mathias Weller
4. On the Complexity of Detecting \(k\)-Length Negative Cost Cycles
   Longkun Guo and Peng Li
5. An Efficient Primal-Dual Algorithm for Fair Combinatorial Optimization Problems
   Viet Hung Nguyen and Paul Weng

Session 4 Approximation Algorithm, Chair: Michael Khachay (120 Minutes 6 Papers)

1. Approximation Algorithms for Maximum Coverage with Group Budget Constraints
   Longkun Guo, Min Li and Dachuan Xu
2. A Spectral Partitioning Algorithm for Maximum Directed Cut Problem
   Zhenning Zhang, Donglei Du, Chenchen Wu, Dachuan Xu and Dongmei Zhang
3. Approximating \(k\)-Forest with Resource Augmentation: A Primal-Dual Approach
   Eric Angel, Kim Thang Nguyen and Shikha Singh
4. Better Approximation Ratios for the Single-Vehicle Scheduling Problems on Tree/Cycle Networks
   Yuanxiao Wu and Xiwen Lu
5. Parameterized Approximation Algorithms for Some Location Problems in Graphs
   Arne Leitert and Feodor Dragan
6. Efficient Algorithms for Ridesharing of Personal Vehicles
   Qianping Gu, Leo Jiajian Liang and Guochuan Zhang

Session 5 Combinatorial Optimization, Chair: Viet Hung Nguyen (120 Minutes 6 Papers)

1. A New Graph Parameter to Measure Linearity
   Pierre Charbit, Michel Habib, Lalla Mouatadid and Reza Naserasr
2. Faster and Enhanced Inclusion-Minimal Cograph Completion
   Christophe Crespelle, Daniel Lokshtanov, Thi Ha Duong Phan and Eric Thierry
3. Graph Editing to a Given Neighbourhood Degree List is Fixed-Parameter Tractable
   Naomi Nishimura and Vijay Subramanya
4. Lexico-Minimum Replica Placement in Multitrees
   K. Alex Mills, R. Chandrasekaran and Neeraj Mittal
5. Structure of Towers and a New Proof of the Tight Cut Lemma
   Nanao Kita
6. Price Fluctuation in Online Leasing
   Christine Markarian, Bjorn Feldkord and Friedhelm Meyer Auf der Heide

Session 6 Combinatorial Optimization, Chair: Alireza Zarei (100 Minutes 5 Papers)

1. Algorithms for the Ring Star Problem
   Xujin Chen, Xiaodong Hu, Zhongzheng Tang, Chenhao Wang and Ying Zhang
2. Floorplans with Columns
   Katsuhisa Yamanaka, Md. Saidur Rahman and Shin-Ichi Nakano
3. On the Profit-Maximizing for Transaction Platforms in Crowd Sensing
   Xi Luo, Jialiang Lu, Guangshuo Chen, Linghe Kong and Minyou Wu
4. An Efficient Algorithm for Judicious Partition of Hypergraphs
   Tunzi Tan, Jihong Gui, Sainan Wang, Suixiang Gao and Wenguo Yang
5. A Refined Characteristic of Minimum Contingency Set for Conjunctive Query
   Dongjing Miao and Zhipeng Cai

Session 7 Application, Chair: Ugo Vaccaro (100 Minutes 5 Papers)

1. Cloning Automata: Simulation and Analysis of Computer Bacteria
   Chu Chen, Zhenhua Duan and Cong Tian
2. Modelling and Solving Anti-aircraft Mission Planning for Defensive Missile Battalions
   Trang Nguyen, Trung Bui, Bang Nguyen and Su Le
3. Perspectives of Big Data Analysis in Urban Railway Planning: Shenzhen Metro Case Study
   Keke Peng, Caiwei Yuan and Wen Xu
4. Repair Position Selection for Inconsistent Data
   Xianmin Liu, Yingshu Li and Jianzhong Li
5. Unbounded One-Way Trading on Distributions with Monotone Hazard Rate
   Francis Chin, Francis Lau, Hing-Fung Ting, Haisheng Tan and Yong Zhang

Session 8 Network, Chair: Neeraj Mittal (120 Minutes 6 Papers)

1. A Framework for Overall Storage Overflow Problem to Maximize the Lifetime in WSNs
   Guoliang Song, Chen Zhang, Chuang Liu and Yuna Chai
2. A Parallel Construction of Vertex-disjoint Spanning Trees with Optimal Heights in Star Networks
   Shih-Shun Kao, Jou-Ming Chang, Kung-Jui Pai, Jinn-Shyong Yang, Shyue-Ming Tang and Ro-Yu Wu
3. Filtering Undesirable Flows in Networks
   Gleb Polevoy, Stojan Trajanovski, Paola Grosso and Cees de Laat
4. Protein Mover's Distance: A Geometric Approach for Solving Global Alignment of PPI Networks
   Manni Liu and Hu Ding
5. On Interdependent Failure Resilient Multi-path Routing in Smart Grid Communication Network
   Zishen Yang, Donghyun Kim and Wei Wang
6. Toward Energy-Efficient and Robust Clustering Algorithm on Mobile Ad Hoc Sensor Networks
   Huamei Qi, Tailong Xiao, Anfeng Liu and Su Jiang

Session 9 Graph Theory, Chair: Qianping Gu (120 Minutes 6 Papers)

1. Conflict-Free Connection Numbers of Line Graphs
   Bo Deng, Wenjing Li, Xueliang Li, Yaping Mao and Haixing Zhao
2. Hamiltonian Cycles in Covering Graphs of Trees
   Hiroshi Nishiyama, Lasislav Stacho and Pavol Hell
3. Mixed Connectivity of Random Graphs
   Ran Gu, Yongtang Shi and Neng Fan
4. On \(k\)-Strong Conflict-Free Multicoloring
   Luisa Gargano, Adele Rescigno and Ugo Vaccaro
5. The Coloring Reconfiguration Problem on Specific Graph Classes
   Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou
6. Tropical Paths in Vertex-Colored Graphs
   Johanne Cohen, Giuseppe F. Italiano, Yannis Manoussakis, Kim Thang Nguyen and Hong Phong Pham

Session 10 Combinatorial Optimization, Chair: Yannis Manoussakis (100 Minutes 5 Papers)

1. Faster Algorithms for 1-Mappability of A Sequence
   Mai Alzamel, Panagiotis Charalampopoulos, Costas S Iliopoulos, Solon P Pissis, Jakub Radoszewski and Wing-Kin Sung
2. Improved Methods for Computing Distances between Unordered Trees Using Integer Programming
   Eunpyeong Hong, Yasuaki Kobayashi and Akihiro Yamamoto
3. Minimizing Total Completion Time of Batch Scheduling with Nonidentical Job Sizes
   Rongqi Li, Zhiyi Tan and Qianyu Zhu
4. Novel Scheduling for Energy Management in Microgrid
   Zaixin Lu, Jd Youngs, Zhi Chen and Miao Pan
5. Touring Convex Polygons In Polygonal Domain Fences
   Amirhossein Mozafari, Alireza Zarei and Arash Ahadi

Session 11 Application, Chair: Francis Y.L. Chin (100 Minutes 5 Papers)

1. A Simple Greedy Algorithm for the Profit-Aware Social Team Formation Problem
   Shengxin Liu and Chung Keung Poon
2. Bounds for Static Black-Peg AB Mastermind
   Christian Glazik, Gerold Jager, Jan Schiemann and Anand Srivastav
3. Classication Statistics in RFID Systems
   Zhenzao Wen, Jiapeng Huang, Linghe Kong, Min-You Wu and Guihai Chen
4. Doctor Rostering in Compliance with the New UK Junior Doctor Contract
   Anna Lavygina, Kristopher Welsh and Alan Crispin
5. Generalized Bidirectional Limited Magnitude Error Correcting Code for MLC Flash Memories
   Akram Hussain, Xinchun Yu and Yuan Luo

Session 12 Demo and Application (Fast Track), Chair: Xiaofei Liu (80 Minutes 8 Papers)

1. A Local Search Approximation Algorithm for A Squared Metric \(k\)-Facility Location Problem
   Dongmei Zhang, Dachuan Xu, Yishui Wang, Peng Zhang and Zhenning Zhang
2. A New Approximation Algorithm for the Maximum Stacking Base Pairs Problem from RNA Secondary Structures Prediction
   Aizhong Zhou, Haitao Jiang, Jiong Guo and Daming Zhu
3. Approximation Algorithms for the Generalized Stacker Crane Problem
   Jianping Li, Xiaofei Liu, Weidong Li and Li Guan
4. Combinatorial Approximation algorithms for Spectrum Assignment Problem in Chain and Ring Networks
   Guangting Chen, Lei Zhang, An Zhang and Yong Chen
5. Fast Approximation Algorithms for Computing Constrained Minimum Spanning Tree
   Pei Yao and Longkun Guo
6. Longest Previous non-overlapping Factors Table Computation
   Supaporn Chairungsee and Maxime Crochemore
7. Online Algorithms for Non-preemptive Speed Scaling on Power-Heterogeneous Processors
   Aeshah Alsughayyir and Thomas Erlebach
8. The Euclidean Vehicle Routing Problem with Multiple Depots and Time Windows
   Liang Song and Hejiao Huang

Session 13 Demo and Application (Fast Track), Chair: Boting Yang (80 Minutes 8 Papers)

1. Research on Arrival Integration method for Point Merge System in Tactical Operation
   Yannan Qi, Xinglong Wang and Chen Chen
2. A Memetic Algorithm for the Linear Ordering Problem with Cumulative Costs
   Taoqing Zhou, Zhipeng Lu, Tao Ye and Kan Zhou
3. Modeling and Verifying Multi-Core Programs
   Nan Zhang and Zhenhua Duan
4. On Adaptive Bitprobe Schemes for Storing Two Elements
   Deepanjan Kesh
5. On the Linearization of Scaffolds sharing Repeated Contigs
   Mathias Weller, Annie Chateau and Rodolphe Giroudeau
6. On Structural Parameterizations of the Matching Cut Problem
   N R Aravind, Subrahmanyam Kalyanasundaram and Anjeneya Swami Kare
7. Optimal Topology Design of High Altitude Platform based Maritime Broadband Communication Networks
   Jianli Duan, Tiange Zhao and Bin Lin
8. Planar Vertex-Disjoint Cycle Packing: New Structures and Improved Kernel
   Qilong Feng, Xiaolu Liao and Jianxin Wang