The \(k\)-separator problem: polyhedra, complexity and approximation results
From MaRDI portal
Publication:2354313
DOI10.1007/s10878-014-9753-xzbMath1348.90589OpenAlexW2113048862MaRDI QIDQ2354313
Walid Ben-Ameur, Mohamed-Ahmed Mohamed-Sidi, José Neto
Publication date: 10 July 2015
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-014-9753-x
Related Items (11)
Linear kernels for separating a graph into components of bounded size ⋮ Unnamed Item ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ Parameterized Complexity of Safe Set ⋮ The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut ⋮ A compact mixed integer linear formulation for safe set problems ⋮ Unnamed Item ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Political districting to minimize cut edges
Cites Work
- Unnamed Item
- Unnamed Item
- Maximum weight independent sets and cliques in intersection graphs of filaments
- Weakly triangulated graphs
- On the hardness of approximating minimum vertex cover
- Some results on graphs without long induced paths
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- On the dimension of projected polyhedra
- Treewidth. Computations and approximations
- \(k\)-edge subgraph problems
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- The primal-dual method for approximation algorithms
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Algorithms for weakly triangulated graphs
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- The complexity of dissociation set problems in graphs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- The vertex separator problem: a polyhedral investigation
- Independent packings in structured graphs
- Easy problems for tree-decomposable graphs
- On graphs with polynomially solvable maximum-weight clique problem
- Node-Deletion Problems on Bipartite Graphs
- The complexity of restricted spanning tree problems
- Decomposing Matrices into Blocks
- Independent Sets in Asteroidal Triple-Free Graphs
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- The k-Separator Problem
- A linear time algorithm for finding tree-decompositions of small treewidth
- Disconnecting graphs by removing vertices: a polyhedral approach
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Combinatorial optimization. Theory and algorithms.
This page was built for publication: The \(k\)-separator problem: polyhedra, complexity and approximation results
