Complexity and approximability of the k‐way vertex cut

DOI10.1002/net.21534zbMath1386.05148OpenAlexW2044757908WikidataQ57338948 ScholiaQ57338948MaRDI QIDQ4639693

Ruben van der Zwaan, Alexander Grigoriev, André Berger

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40)

Related Items (10)

Critical node detection problem for complex network in undirected weighted networks ⋮ The bi-objective critical node detection problem ⋮ The connected critical node problem ⋮ Critical node/edge detection problems on trees ⋮ The vertex \(k\)-cut problem ⋮ The firebreak problem ⋮ On integer and bilevel formulations for the \(k\)-vertex cut problem ⋮ The critical node detection problem in networks: a survey ⋮ A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs ⋮ The Critical Node Problem Based on Connectivity Index and Properties of Components on Trees

This page was built for publication: Complexity and approximability of the k‐way vertex cut