Algorithms and Complexity 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings

This book constitutes the refereed conference proceedings of the 9th International Conference on Algorithms and Complexity, CIAC 2015, held in Paris, France, in May 2015.

Communication, Dynamics and Renormalization.- Fast and Powerful Hashing using Tabulation.- Green Barrier Coverage with Mobile Sensors.- A Re?ned Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths.- Orthogonal Graph Drawing with In?exible Edges.- Linear time Constructions of some d-Restriction Problems.- E?ciently Testing T-Interval Connectivity in Dynamic Graphs.- Competitive Strategies for Online Clique Clustering.- Scheduling with Gaps: New Models and Algorithms.- MinMax-Distance Gathering on given Meeting Points.- Evacuating Robots from a Disk Using Face-to-Face Communication.- Planarity of Streamed Graphs.- Clique-width of Graph Classes De?ned by Two Forbidden Induced Subgraphs.- Randomized Adaptive Test Cover.- Contraction Blockers for Graphs with Forbidden Induced Paths.- Label Placement in Road Maps.- Discrete Stochastic Submodular Maximization: Adaptive vs. Non-Adaptive vs. O?ine.- Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints.- Simple strategies versus optimal schedules in multi-agent patrolling.- Sharing Non-Anonymous Costs of Multiple Resources Optimally.- Algorithms solving the Matching Cut problem.- End-Vertices of Graph Search Algorithms.- Deciding the On-line Chromatic Number of a Graph with Pre-coloring is PSPACE-complete.- A Lex-BFS-based recognition algorithm for Robinsonian matrices.- Mixed Map Labeling.- Optimal Online Edge Coloring of Planar Graphs with Advice.- Approximability of Two Variants of Multiple Knapsack.- Block Sorting is Hard.- An opportunistic text indexing structure based on run length encoding.- PSPACE-completeness of Bloxorz and of Games with 2-Buttons.- Advice Complexity of Fine-Grained Job Shop Scheduling.