Partitioning a graph into small pieces with applications to path transversal
From MaRDI portal
Publication:2316611
DOI10.1007/s10107-018-1255-7zbMath1452.68137arXiv1607.05122OpenAlexW3014552119MaRDI QIDQ2316611
Publication date: 6 August 2019
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.05122
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
Component order connectivity in directed graphs, Treewidth versus clique number. II: Tree-independence number, Parameterized Complexity of Safe Set, Component order connectivity in directed graphs, Unnamed Item, Approximating the discrete time-cost tradeoff problem with bounded depth, Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size, Vertex cover at distance on \(H\)-free graphs, Approximation algorithms for hitting subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the computational complexity of vertex integrity and component order connectivity
- Balanced graph partitioning
- A faster FPT algorithm for 3-path vertex cover
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- Minimum \(k\)-path vertex cover
- The complexity of dissociation set problems in graphs
- The \(k\)-separator problem: polyhedra, complexity and approximation results
- On the vertex \(k\)-path cover
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Fixed-Parameter and Approximation Algorithms: A New Look
- Detecting high log-densities
- Divide-and-conquer approximation algorithms via spreading metrics
- Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs
- A new multilayered PCP and the hardness of hypergraph vertex cover
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Node-Deletion Problems on Bipartite Graphs
- The complexity of restricted spanning tree problems
- Fast Approximate Graph Partitioning Algorithms
- Approximation Algorithms for the 0-Extension Problem
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Inapproximability of H-Transversal/Packing
- Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
- Expander flows, geometric embeddings and graph partitioning
