How to Cut a Graph into Many Pieces

DOI10.1007/978-3-642-20877-5_20MaRDI QIDQ3010400zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• scientific article; zbMATH DE number 2104823
• Cutting a graph into two dissimilar halves
• Cutting two graphs simultaneously
• Graphs of plural cuts
• scientific article; zbMATH DE number 3876616
• Split graphs
• Split graphs
• How to cut pseudoparabolas into segments
• Labeled cuts in graphs
• Dividing a graph by degrees

Cites work

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

Cited in

(6)

• Critical node detection problem for complex network in undirected weighted networks
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Cutting a graph into two dissimilar halves
• An integer programming framework for critical elements detection in graphs
• Detecting critical node structures on graphs: a mathematical programming approach
• Complexity and approximability of the \(k\)-way vertex cut

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

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