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)

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

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)