Ebook: Algorithms and Complexity: 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings

This book constitutes the refereed conference proceedings of the 8th International Conference on Algorithms and Complexity, CIAC 2013, held in Barcelona, Spain, during May 22-24, 2013. The 31 revised full papers presented were carefully reviewed and selected from 75 submissions. The papers present current research in all aspects of computational complexity and the use, design, analysis and experimentation of efficient algorithms and data structures.

---

This book constitutes the refereed conference proceedings of the 8th International Conference on Algorithms and Complexity, CIAC 2013, held in Barcelona, Spain, during May 22-24, 2013. The 31 revised full papers presented were carefully reviewed and selected from 75 submissions. The papers present current research in all aspects of computational complexity and the use, design, analysis and experimentation of efficient algorithms and data structures.

---

This book constitutes the refereed conference proceedings of the 8th International Conference on Algorithms and Complexity, CIAC 2013, held in Barcelona, Spain, during May 22-24, 2013. The 31 revised full papers presented were carefully reviewed and selected from 75 submissions. The papers present current research in all aspects of computational complexity and the use, design, analysis and experimentation of efficient algorithms and data structures.
Content:
Front Matter....Pages -
Approximation Algorithms for Disjoint st-Paths with Minimum Activation Cost....Pages 1-12
Parameterized Complexity and Kernel Bounds for Hard Planning Problems....Pages 13-24
Selfish Resource Allocation in Optical Networks....Pages 25-36
Average Optimal String Matching in Packed Strings....Pages 37-48
Parameterized Complexity of DAG Partitioning....Pages 49-60
Four Measures of Nonlinearity....Pages 61-72
On the Characterization of Plane Bus Graphs....Pages 73-84
Online Multi-dimensional Dynamic Bin Packing of Unit-Fraction Items....Pages 85-96
A Greedy Approximation Algorithm for Minimum-Gap Scheduling....Pages 97-109
Exponential Complexity of Satisfiability Testing for Linear-Size Boolean Formulas....Pages 110-121
Linear Time Distributed Swap Edge Algorithms....Pages 122-133
Decentralized Throughput Scheduling....Pages 134-145
New Results on Stabbing Segments with a Polygon....Pages 146-157
Complexity of Barrier Coverage with Relocatable Sensors in the Plane....Pages 158-169
Succinct Permanent Is NEXP-Hard with Many Hard Instances....Pages 170-182
Money-Based Coordination of Network Packets....Pages 183-196
Truthful Many-to-Many Assignment with Private Weights....Pages 197-208
Competitive Online Clique Clustering....Pages 209-220
Optimal Network Decontamination with Threshold Immunity....Pages 221-233
Finding All Convex Cuts of a Plane Graph in Cubic Time....Pages 234-245
Shortest Paths with Bundles and Non-additive Weights Is Hard....Pages 246-263
Cliques and Clubs....Pages 264-275
List Coloring in the Absence of Two Subgraphs....Pages 276-287
Query Complexity of Matroids....Pages 288-299
A New Dynamic Graph Structure for Large-Scale Transportation Networks....Pages 300-311
Capacitated Rank-Maximal Matchings....Pages 312-323
A Faster CREW PRAM Algorithm for Computing Cartesian Trees....Pages 324-335
Advice Complexity of the Online Coloring Problem....Pages 336-344
Sparse Linear Complementarity Problems....Pages 345-357
LP-Rounding Algorithms for the Fault-Tolerant Facility Placement Problem....Pages 358-369
Back Matter....Pages 370-381
....Pages -