How to Cut a Graph into Many Pieces

DOI10.1007/978-3-642-20877-5_20zbMath1331.68117OpenAlexW1753901987MaRDI QIDQ3010400

Ruben van der Zwaan, Alexander Grigoriev, André Berger

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_20

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (4)

Critical node detection problem for complex network in undirected weighted networks ⋮ An integer programming framework for critical elements detection in graphs ⋮ Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth ⋮ Detecting critical node structures on graphs: A mathematical programming approach

Cites Work

• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• Parameterized graph separation problems
• Simple and improved parameterized algorithms for multiterminal cuts
• Optimization, approximation, and complexity classes
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth. Computations and approximations
• A note on the bounded fragmentation property and its applications in network reliability
• An improved approximation algorithm of MULTIWAY CUT.
• Approximation algorithms for minimum \(K\)-cut
• An improved parameterized algorithm for the minimum node multiway cut problem
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Finding small balanced separators
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Efficient Planarity Testing
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Approximation algorithms for NP-complete problems on planar graphs
• The Complexity of Multiterminal Cuts
• Finding k Cuts within Twice the Optimal
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Multiway cuts in node weighted graphs
• The Valve Location Problem in Simple Network Topologies
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: How to Cut a Graph into Many Pieces