Complexity and approximability of the k-way vertex cut

DOI10.1002/NET.21534MaRDI QIDQ4639693zbMATH OpenOpenAlexWikidataFDO

Authors André Berger, Alexander Grigoriev, Ruben van der Zwaan

Publication date 11 May 2018

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.21534

zbMATH Keywords

computational complexityconnectivityplanar graphapproximation schemeseparator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• How to Cut a Graph into Many Pieces
• Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs
• The k-separator problem: polyhedra, complexity and approximation results
• The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
• Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems

Cited in

(19)

• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• On the complexity of finding balanced oneway cuts
• The vertex \(k\)-cut problem
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Critical node detection problem for complex network in undirected weighted networks
• A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
• On algorithms employing treewidth for \(L\)-bounded cut problems
• Critical node/edge detection problems on trees
• On integer and bilevel formulations for the \(k\)-vertex cut problem
• The firebreak problem
• The critical node problem based on connectivity index and properties of components on trees
• Breaking the n ^k barrier for minimum k -cut on simple graphs
• The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
• The connected critical node problem
• scientific article; zbMATH DE number 6850403 (Why is no real title available?)
• The bi-objective critical node detection problem
• The critical node detection problem in networks: a survey
• The k-separator problem: polyhedra, complexity and approximation results

This page was built for publication: Complexity and approximability of the \(k\)-way vertex cut

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