Partitioning a Graph into Small Pieces with Applications to Path Transversal

DOI10.1137/1.9781611974782.101zbMath1410.68303OpenAlexW2952332314MaRDI QIDQ4575844

Euiwoong Lee

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.101

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items

Inapproximability of $H$-Transversal/Packing, Strong hardness of approximation for tree transversals, Computing connected-\(k\)-subgraph cover with connectivity requirement, Approximation algorithm for minimum weight connected-\(k\)-subgraph cover, Unnamed Item, The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut, Approximation algorithm for minimum connected 3-path vertex cover, Approximation algorithms for minimum weight connected 3-path vertex cover, Unnamed Item, Unnamed Item, Approximating Partially Bounded Degree Deletion on Directed Graphs, Political districting to minimize cut edges