Combinatorial Algorithms: 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings

Front Matter....Pages I-XX
Front Matter....Pages 1-1
On the Complexity of Computing Treebreadth....Pages 3-15
Online Chromatic Number is PSPACE-Complete....Pages 16-28
Front Matter....Pages 29-29
Bounded Embeddings of Graphs in the Plane....Pages 31-42
Crushing Disks Efficiently....Pages 43-54
Essential Constraints of Edge-Constrained Proximity Graphs....Pages 55-67
Plane Bichromatic Trees of Low Degree....Pages 68-80
Front Matter....Pages 81-81
Directing Road Networks by Listing Strong Orientations....Pages 83-95
Evangelism in Social Networks....Pages 96-108
Distance Queries in Large-Scale Fully Dynamic Complex Networks....Pages 109-121
Minimax Regret 1-Median Problem in Dynamic Path Networks....Pages 122-134
Front Matter....Pages 135-135
On Maximal Chain Subgraphs and Covers of Bipartite Graphs....Pages 137-150
Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations....Pages 151-162
Reconfiguration of Steiner Trees in an Unweighted Graph....Pages 163-175
Front Matter....Pages 177-177
Weighted Online Problems with Advice....Pages 179-190
Finding Gapped Palindromes Online....Pages 191-202
Advice Complexity of the Online Search Problem....Pages 203-212
Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing....Pages 213-225
Front Matter....Pages 227-227
A Boundary Property for Upper Domination....Pages 229-240
Upper Domination: Complexity and Approximation....Pages 241-252
Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes....Pages 253-265
Front Matter....Pages 227-227
Sufficient Conditions for Tuza’s Conjecture on Packing and Covering Triangles....Pages 266-277
Front Matter....Pages 279-279
Linear Time Algorithms for Happy Vertex Coloring Problems for Trees....Pages 281-292
Speeding up Dynamic Programming in the Line-Constrained k-median....Pages 293-305
Front Matter....Pages 307-307
SOBRA - Shielding Optimization for BRAchytherapy....Pages 309-320
A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints....Pages 321-333
Limits of Greedy Approximation Algorithms for the Maximum Planar Subgraph Problem....Pages 334-346
Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs....Pages 347-358
Front Matter....Pages 359-359
Finding Cactus Roots in Polynomial Time....Pages 361-372
Computing Giant Graph Diameters....Pages 373-384
Faster Computation of Path-Width....Pages 385-396
The Solution Space of Sorting with Recurring Comparison Faults....Pages 397-408
Front Matter....Pages 409-409
Monotone Paths in Geometric Triangulations....Pages 411-422
On Computing the Total Displacement Number via Weighted Motzkin Paths....Pages 423-434
Front Matter....Pages 435-435
Partial Covering Arrays: Algorithms and Asymptotics....Pages 437-448
Querying Probabilistic Neighborhoods in Spatial Data Sets Efficiently....Pages 449-460
Back Matter....Pages 461-462