Partitioning a graph into small pieces with applications to path transversal

DOI10.1137/1.9781611974782.101zbMATH Open1410.68303OpenAlexW2952332314MaRDI QIDQ4575844FDOQ4575844

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

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

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)

Cited In (15)

• Title not available (Why is that?)
• Partitioning a graph into small pieces with applications to path transversal
• Inapproximability of \(H\)-transversal/packing
• Sherali-Adams integrality gaps matching the log-density threshold
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
• Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
• Title not available (Why is that?)
• 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)