Complexity and approximability of the k-way vertex cut

DOI10.1002/NET.21534zbMATH Open1386.05148OpenAlexW2044757908WikidataQ57338948 ScholiaQ57338948MaRDI QIDQ4639693FDOQ4639693

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

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

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)

Cited In (19)

• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• The vertex \(k\)-cut problem
• On the complexity of finding balanced oneway cuts
• 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
• Title not available (Why is that?)
• 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)