Algorithms and Complexity: 12th International Conference, Ciac 2021, Virtual Event, May 10-12, 2021, Proceedings

ISBN-13: 9783030752415 / Angielski / Miękka / 2021 / 410 str.

Tiziana Calamoneri; Federico Cor?

Spis treści

Abundant Extensions.- Three Problems on Well-Partitioned Chordal Graphs.- Distributed Distance-r Covering Problems on Sparse High-Girth Graphs.- Reconfiguration of Connected Graph Partitions via Recombination.- Algorithms for Energy Conservation in Heterogeneous Data Centers.- On Vertex-Weighted Graph Realizations.- On the Role of 3's for the 1-2-3 Conjecture.- Upper Tail Analysis of Bucket Sort and Random Tries.- Throughput Scheduling with Equal Additive Laxity.- Fragile Complexity of Adaptive Algorithms.- FPT and Kernelization Algorithms for the Induced Tree Problem.- A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs.- Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation.- A Multistage View on 2-Satisfiability.- The Weisfeiler-Leman Algorithm and Recognition of Graph Properties.- The Parameterized Suffix Tray.- Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity.- Covering a Set of Line Segments with a Few Squares.- Circumventing Connectivity for Kernelization.- Online and Approximate Network Construction from Bounded Connectivity Constraints.- Globally Rigid Augmentation of Minimally Rigid Graphs in \(R^2\).- Extending Partial Representations of Rectangular Duals with Given Contact Orientations.- Can Local Optimality be Used for Efficient Data Reduction.- Colouring Graphs of Bounded Diameter in the Absence of Small Cycles.- Online Two-Dimensional Vector Packing with Advice.- Temporal Matching on Geometric Graph Data.