Computing and Combinatorics : 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings

Front Matter ....Pages I-XXI
Front Matter ....Pages 1-1
 A Time-Space Trade-Off for Triangulations of Points in the Plane  (Hee-Kap Ahn, Nicola Baraldo, Eunjin Oh, Francesco Silvestri)....Pages 3-12
 An FPTAS for the Volume of Some \(\mathcal{V}\)-polytopes—It is Hard to Compute the Volume of the Intersection of Two Cross-Polytopes  (Ei Ando, Shuji Kijima)....Pages 13-24
 Local Search Strikes Again: PTAS for Variants of Geometric Covering and Packing  (Pradeesha Ashok, Aniket Basu Roy, Sathish Govindarajan)....Pages 25-37
 Depth Distribution in High Dimensions  (Jérémy Barbay, Pablo Pérez-Lantero, Javiel Rojas-Ledesma)....Pages 38-49
 An Improved Lower Bound on the Growth Constant of Polyiamonds  (Gill Barequet, Mira Shalah, Yufei Zheng)....Pages 50-61
 Constrained Routing Between Non-Visible Vertices  (Prosenjit Bose, Matias Korman, André van Renssen, Sander Verdonschot)....Pages 62-74
 Deletion Graph Problems Based on Deadlock Resolution  (Alan Diêgo Aurélio Carneiro, Fábio Protti, Uéverton S. Souza)....Pages 75-86
 Space-Efficient Algorithms for Maximum Cardinality Search, Stack BFS, Queue BFS and Applications  (Sankardeep Chakraborty, Srinivasa Rao Satti)....Pages 87-98
 Efficient Enumeration of Non-Equivalent Squares in Partial Words with Few Holes  (Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski et al.)....Pages 99-111
 The Approximability of the p-hub Center Problem with Parameterized Triangle Inequality  (Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing)....Pages 112-123
 Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem  (Zhi-Zhong Chen, Guohui Lin, Lusheng Wang, Yong Chen, Dan Wang)....Pages 124-136
 Incentive Ratios of a Proportional Sharing Mechanism in Resource Sharing  (Zhou Chen, Yukun Cheng, Qi Qi, Xiang Yan)....Pages 137-149
 Efficient Enumeration of Maximal k-Degenerate Subgraphs in a Chordal Graph  (Alessio Conte, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, Kunihiro Wasa)....Pages 150-161
 Reoptimization of Minimum Latency Problem  (Wenkai Dai)....Pages 162-174
 Pure Nash Equilibria in Restricted Budget Games  (Maximilian Drees, Matthias Feldotto, Sören Riechers, Alexander Skopalik)....Pages 175-187
 A New Kernel for Parameterized Max-Bisection Above Tight Lower Bound  (Qilong Feng, Senmin Zhu, Jianxin Wang)....Pages 188-199
 Information Complexity of the AND Function in the Two-Party and Multi-party Settings  (Yuval Filmus, Hamed Hatami, Yaqiao Li, Suzin You)....Pages 200-211
 Optimal Online Two-Way Trading with Bounded Number of Transactions  (Stanley P. Y. Fung)....Pages 212-223
 Parameterized Shifted Combinatorial Optimization  (Jakub Gajarský, Petr Hliněný, Martin Koutecký, Shmuel Onn)....Pages 224-236
 Approximate Minimum Diameter  (Mohammad Ghodsi, Hamid Homapour, Masoud Seddighin)....Pages 237-249
 On Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction  (Purnata Ghosal, Om Prakash, B. V. Raghavendra Rao)....Pages 250-261
 A Tighter Relation Between Sensitivity Complexity and Certificate Complexity  (Kun He, Qian Li, Xiaoming Sun)....Pages 262-274
 Unfolding Some Classes of Orthogonal Polyhedra of Arbitrary Genus  (Kuan-Yi Ho, Yi-Jun Chang, Hsu-Chun Yen)....Pages 275-286
 Reconfiguration of Maximum-Weight b-Matchings in a Graph  (Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto)....Pages 287-296
 Constant Approximation for Stochastic Orienteering Problem with \((1+\epsilon )\)-Budget Relaxiation  (Yiyao Jiang)....Pages 297-308
 Quantum Query Complexity of Unitary Operator Discrimination  (Akinori Kawachi, Kenichi Kawano, François Le Gall, Suguru Tamaki)....Pages 309-320
 Randomized Incremental Construction for the Hausdorff Voronoi Diagram Revisited and Extended  (Elena Khramtcova, Evanthia Papadopoulou)....Pages 321-332
 NP-completeness Results for Partitioning a Graph into Total Dominating Sets  (Mikko Koivisto, Petteri Laakkonen, Juho Lauri)....Pages 333-345
 Strong Triadic Closure in Cographs and Graphs of Low Maximum Degree  (Athanasios L. Konstantinidis, Stavros D. Nikolopoulos, Charis Papadopoulos)....Pages 346-358
 Hardness and Structural Results for Half-Squares of Restricted Tree Convex Bipartite Graphs  (Hoang-Oanh Le, Van Bang Le)....Pages 359-370
 Faster Graph Coloring in Polynomial Space  (Serge Gaspers, Edward J. Lee)....Pages 371-383
 On the Modulo Degree Complexity of Boolean Functions  (Qian Li, Xiaoming Sun)....Pages 384-395
 Approximating Weighted Duo-Preservation in Comparative Genomics  (Saeed Mehrabi)....Pages 396-406
 An Incentive Compatible, Efficient Market for Air Traffic Flow Management  (Ruta Mehta, Vijay V. Vazirani)....Pages 407-419
 Linear Representation of Transversal Matroids and Gammoids Parameterized by Rank  (Pranabendu Misra, Fahad Panolan, M. S. Ramanujan, Saket Saurabh)....Pages 420-432
 Dynamic Rank-Maximal Matchings  (Prajakta Nimbhorkar, Arvind Rameshwar V.)....Pages 433-444
 Bend Complexity and Hamiltonian Cycles in Grid Graphs  (Rahnuma Islam Nishat, Sue Whitesides)....Pages 445-456
 Optimal Covering and Hitting of Line Segments by Two Axis-Parallel Squares  (Sanjib Sadhu, Sasanka Roy, Subhas C. Nandy, Suchismita Roy)....Pages 457-468
 Complexity and Algorithms for Finding a Subset of Vectors with the Longest Sum  (Vladimir Shenmaier)....Pages 469-480
 Simple \(O(n~log^{2}~n)\) Algorithms for the Planar 2-Center Problem  (Xuehou Tan, Bo Jiang)....Pages 481-491
 Stable Matchings in Trees  (Satoshi Tayu, Shuichi Ueno)....Pages 492-503
 Maximum Matching on Trees in the Online Preemptive and the Incremental Dynamic Graph Models  (Sumedh Tirodkar, Sundar Vishwanathan)....Pages 504-515
 Approximation Algorithms for Scheduling Multiple Two-Stage Flowshops  (Guangwei Wu, Jianxin Wang)....Pages 516-528
 The Existence of Universally Agreed Fairest Semi-matchings in Any Given Bipartite Graph  (Jian Xu, Soumya Banerjee, Wenjing Rao)....Pages 529-541
 Better Inapproximability Bounds and Approximation Algorithms for Min-Max Tree/Cycle/Path Cover Problems  (Wei Yu, Zhaohui Liu)....Pages 542-554
 On the Complexity of k-Metric Antidimension Problem and the Size of k-Antiresolving Sets in Random Graphs  (Congsong Zhang, Yong Gao)....Pages 555-567
 A Local Search Approximation Algorithm for the k-means Problem with Penalties  (Dongmei Zhang, Chunlin Hao, Chenchen Wu, Dachuan Xu, Zhenning Zhang)....Pages 568-574
 Improved Approximation Algorithm for the Maximum Base Pair Stackings Problem in RNA Secondary Structures Prediction  (Aizhong Zhou, Haitao Jiang, Jiong Guo, Haodi Feng, Nan Liu, Binhai Zhu)....Pages 575-587
Front Matter ....Pages 589-589
 Cooperative Game Theory Approaches for Network Partitioning  (Konstantin E. Avrachenkov, Aleksei Yu. Kondratev, Vladimir V. Mazalov)....Pages 591-602
 Chain of Influencers: Multipartite Intra-community Ranking  (Pavla Drazdilova, Jan Konecny, Milos Kudelka)....Pages 603-614
 Influence Spread in Social Networks with both Positive and Negative Influences  (Jing (Selena) He, Ying Xie, Tianyu Du, Shouling Ji, Zhao Li)....Pages 615-629
 Guided Genetic Algorithm for the Influence Maximization Problem  (Pavel Krömer, Jana Nowaková)....Pages 630-641
 Optimal Local Routing Strategies for Community Structured Time Varying Communication Networks  (Suchi Kumari, Anurag Singh, Hocine Cherifi)....Pages 642-653
 Graph Construction Based on Local Representativeness  (Eliska Ochodkova, Sarka Zehnalova, Milos Kudelka)....Pages 654-665
 SHADE Algorithm Dynamic Analyzed Through Complex Network  (Adam Viktorin, Roman Senkerik, Michal Pluhacek, Tomas Kadavy)....Pages 666-677
 An Efficient Potential Member Promotion Algorithm in Social Networks via Skyline  (Siman Zhang, Jiping Zheng)....Pages 678-690
Back Matter ....Pages 691-693