Partitioning a graph into small pieces with applications to path transversal

DOI10.1137/1.9781611974782.101MaRDI QIDQ4575844zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Partitioning a graph into small pieces with applications to path transversal
• The k-separator problem: polyhedra, complexity and approximation results
• Finding small balanced separators
• Approximating small balanced vertex separators in almost linear time
• The \(k\)-separator problem

Cited in

(15)

• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Inapproximability of \(H\)-transversal/packing
• Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
• Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
• Political districting to minimize cut edges
• Strong hardness of approximation for tree transversals
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• Approximation algorithm for minimum connected 3-path vertex cover
• scientific article; zbMATH DE number 7559088 (Why is no real title available?)
• scientific article; zbMATH DE number 7525474 (Why is no real title available?)
• Sherali-Adams integrality gaps matching the log-density threshold
• Approximation algorithms for minimum weight connected 3-path vertex cover
• The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
• Partitioning a graph into small pieces with applications to path transversal
• Approximating partially bounded degree deletion on directed graphs

This page was built for publication: Partitioning a graph into small pieces with applications to path transversal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575844)