Computing and Combinatorics

Front Matter ....Pages I-XIX
 Constructing Independent Spanning Trees on Bubble-Sort Networks  (Shih-Shun Kao, Jou-Ming Chang, Kung-Jui Pai, Ro-Yu Wu)....Pages 1-13
 Exact Algorithms for Finding Partial Edge-Disjoint Paths  (Yunyun Deng, Longkun Guo, Peihuang Huang)....Pages 14-25
 A Randomized FPT Approximation Algorithm for Maximum Alternating-Cycle Decomposition with Applications  (Haitao Jiang, Lianrong Pu, Letu Qingge, David Sankoff, Binhai Zhu)....Pages 26-38
 Contextual Dependent Click Bandit Algorithm for Web Recommendation  (Weiwen Liu, Shuai Li, Shengyu Zhang)....Pages 39-50
 LP-Based Pivoting Algorithm for Higher-Order Correlation Clustering  (Takuro Fukunaga)....Pages 51-62
 Approximation Algorithms for a Two-Phase Knapsack Problem  (Kameng Nip, Zhenbo Wang)....Pages 63-75
 More Routes for Evacuation  (Katsuhisa Yamanaka, Yasuko Matsui, Shin-ichi Nakano)....Pages 76-83
 Fine-Grained Parameterized Complexity Analysis of Knot-Free Vertex Deletion – A Deadlock Resolution Graph Problem  (Alan Diêgo Aurélio Carneiro, Fábio Protti, Uéverton S. Souza)....Pages 84-95
 Approximating Global Optimum for Probabilistic Truth Discovery  (Shi Li, Jinhui Xu, Minwei Ye)....Pages 96-107
 Online Interval Scheduling to Maximize Total Satisfaction  (Koji M. Kobayashi)....Pages 108-119
 Properties of Minimal-Perimeter Polyominoes  (Gill Barequet, Gil Ben-Shachar)....Pages 120-129
 Computing Convex-Straight-Skeleton Voronoi Diagrams for Segments and Convex Polygons  (Gill Barequet, Minati De, Michael T. Goodrich)....Pages 130-142
 Polygon Queries for Convex Hulls of Points  (Eunjin Oh, Hee-Kap Ahn)....Pages 143-155
 Synergistic Solutions for Merging and Computing Planar Convex Hulls  (Jérémy Barbay, Carlos Ochoa)....Pages 156-167
 Cophenetic Distances: A Near-Linear Time Algorithmic Framework  (Paweł Górecki, Alexey Markin, Oliver Eulenstein)....Pages 168-179
 Computing Coverage Kernels Under Restricted Settings  (Jérémy Barbay, Pablo Pérez-Lantero, Javiel Rojas-Ledesma)....Pages 180-191
 Weak Mitoticity of Bounded Disjunctive and Conjunctive Truth-Table Autoreducible Sets  (Liyu Zhang, Mahmoud Quweider, Hansheng Lei, Fitra Khan)....Pages 192-204
 Approximation Algorithms for Two-Machine Flow-Shop Scheduling with a Conflict Graph  (Yinhui Cai, Guangting Chen, Yong Chen, Randy Goebel, Guohui Lin, Longcheng Liu et al.)....Pages 205-217
 On Contact Representations of Directed Planar Graphs  (Chun-Hsiang Chan, Hsu-Chun Yen)....Pages 218-229
 Computation and Growth of Road Network Dimensions  (Johannes Blum, Sabine Storandt)....Pages 230-241
 Car-Sharing Between Two Locations: Online Scheduling with Flexible Advance Bookings  (Kelin Luo, Thomas Erlebach, Yinfeng Xu)....Pages 242-254
 Directed Path-Width and Directed Tree-Width of Directed Co-graphs  (Frank Gurski, Carolin Rehs)....Pages 255-267
 Generalized Graph k-Coloring Games  (Raffaello Carosi, Gianpiero Monaco)....Pages 268-279
 On Colorful Bin Packing Games  (Vittorio Bilò, Francesco Cellinese, Giovanna Melideo, Gianpiero Monaco)....Pages 280-292
 Nonbipartite Dulmage-Mendelsohn Decomposition for Berge Duality  (Nanao Kita)....Pages 293-304
 The Path Set Packing Problem  (Chenyang Xu, Guochuan Zhang)....Pages 305-315
 Manipulation Strategies for the Rank-Maximal Matching Problem  (Pratik Ghosal, Katarzyna Paluch)....Pages 316-327
 Finding Maximal Common Subgraphs via Time-Space Efficient Reverse Search  (Alessio Conte, Roberto Grossi, Andrea Marino, Luca Versari)....Pages 328-340
 An FPT Algorithm for Contraction to Cactus  (R. Krithika, Pranabendu Misra, Prafullkumar Tale)....Pages 341-352
 An Approximation Framework for Bounded Facility Location Problems  (Wenchang Luo, Bing Su, Yao Xu, Guohui Lin)....Pages 353-364
 Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect  (Jean Cardinal, Erik D. Demaine, David Eppstein, Robert A. Hearn, Andrew Winslow)....Pages 365-377
 Solving the Gene Duplication Feasibility Problem in Linear Time  (Alexey Markin, Venkata Sai Krishna Teja Vadali, Oliver Eulenstein)....Pages 378-390
 An Efficiently Recognisable Subset of Hypergraphic Sequences  (Syed M. Meesum)....Pages 391-402
 Partial Homology Relations - Satisfiability in Terms of Di-Cographs  (Nikolai Nøjgaard, Nadia El-Mabrouk, Daniel Merkle, Nicolas Wieseke, Marc Hellmuth)....Pages 403-415
 Improved Algorithm for Finding the Minimum Cost of Storing and Regenerating Datasets in Multiple Clouds  (Yingying Wang, Kun Cheng, Zimao Li)....Pages 416-427
 Reconfiguring Spanning and Induced Subgraphs  (Tesshu Hanaka, Takehiro Ito, Haruka Mizuta, Benjamin Moore, Naomi Nishimura, Vijay Subramanya et al.)....Pages 428-440
 Generalizing the Hypergraph Laplacian via a Diffusion Process with Mediators  (T.-H. Hubert Chan, Zhibin Liang)....Pages 441-453
 Efficient Enumeration of Bipartite Subgraphs in Graphs  (Kunihiro Wasa, Takeaki Uno)....Pages 454-466
 Bipartite Graphs of Small Readability  (Rayan Chikhi, Vladan Jovičić, Stefan Kratsch, Paul Medvedev, Martin Milanič, Sofya Raskhodnikova et al.)....Pages 467-479
 Maximum Colorful Cliques in Vertex-Colored Graphs  (Giuseppe F. Italiano, Yannis Manoussakis, Nguyen Kim Thang, Hong Phong Pham)....Pages 480-491
 Partial Sublinear Time Approximation and Inapproximation for Maximum Coverage  (Bin Fu)....Pages 492-503
 Characterizing Star-PCGs  (Mingyu Xiao, Hiroshi Nagamochi)....Pages 504-515
 Liar’s Dominating Set in Unit Disk Graphs  (Ramesh K. Jallu, Sangram K. Jena, Gautam K. Das)....Pages 516-528
 Minimum Spanning Tree of Line Segments  (Sanjana Dey, Ramesh K. Jallu, Subhas C. Nandy)....Pages 529-541
 Improved Learning of k-Parities  (Arnab Bhattacharyya, Ameet Gadekar, Ninad Rajgopal)....Pages 542-553
 On a Fixed Haplotype Variant of the Minimum Error Correction Problem  (Axel Goblet, Steven Kelk, Matúš Mihalák, Georgios Stamoulis)....Pages 554-566
 Non-monochromatic and Conflict-Free Coloring on Tree Spaces and Planar Network Spaces  (Boris Aronov, Mark de Berg, Aleksandar Markovic, Gerhard Woeginger)....Pages 567-578
 Amplitude Amplification for Operator Identification and Randomized Classes  (Debajyoti Bera)....Pages 579-591
 Reconstruction of Boolean Formulas in Conjunctive Normal Form  (Evgeny Dantsin, Alexander Wolpert)....Pages 592-601
 A Faster FPTAS for the Subset-Sums Ratio Problem  (Nikolaos Melissinos, Aris Pagourtzis)....Pages 602-614
 A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time  (Paniz Abedin, Arnab Ganguly, Wing-Kai Hon, Yakov Nekrich, Kunihiko Sadakane, Rahul Shah et al.)....Pages 615-625
 Non-determinism Reduces Construction Time in Active Self-assembly Using an Insertion Primitive  (Benjamin Hescott, Caleb Malchik, Andrew Winslow)....Pages 626-637
 Minimum Membership Hitting Sets of Axis Parallel Segments  (N. S. Narayanaswamy, S. M. Dhannya, C. Ramya)....Pages 638-649
 Minimum Transactions Problem  (Niranka Banerjee, Varunkumar Jayapaul, Srinivasa Rao Satti)....Pages 650-661
 Heuristic Algorithms for the Min-Max Edge 2-Coloring Problem  (Radu Stefan Mincu, Alexandru Popa)....Pages 662-674
 Geometric Spanners in the MapReduce Model  (Sepideh Aghamolaei, Fatemeh Baharifard, Mohammad Ghodsi)....Pages 675-687
 SDP Primal-Dual Approximation Algorithms for Directed Hypergraph Expansion and Sparsest Cut with Product Demands  (T.-H. Hubert Chan, Bintao Sun)....Pages 688-700
 Lower Bounds for Special Cases of Syntactic Multilinear ABPs  (C. Ramya, B. V. Raghavendra Rao)....Pages 701-712
 Approximation Algorithms on Multiple Two-Stage Flowshops  (Guangwei Wu, Jianer Chen)....Pages 713-725
 Constant Factor Approximation Algorithm for l-Pseudoforest Deletion Problem  (Mugang Lin, Bin Fu, Qilong Feng)....Pages 726-737
 New Bounds for Energy Complexity of Boolean Functions  (Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma)....Pages 738-750
 Hitting and Covering Partially  (Akanksha Agrawal, Pratibha Choudhary, Pallavi Jain, Lawqueen Kanesh, Vibha Sahlot, Saket Saurabh)....Pages 751-763
Back Matter ....Pages 765-767