Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width

DOI10.1016/S0196-6774(03)00073-7MaRDI QIDQ4458884zbMATH OpenFDO

Authors Gruia Calinescu, Cristina G. Fernandes, Bruce Reed

Publication date 14 March 2004

Published in Journal of Algorithms (Search for Journal in Brave)

zbMATH Keywords

Approximation algorithmsTree-widthMulticutPolynomial-time approximation schemes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1187148
• Multicuts in unweighted digraphs with bounded degree and bounded tree-width
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• SOFSEM 2006: Theory and Practice of Computer Science
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth

Cited in

(27)

• Disjoint paths in sparse graphs
• Algorithms for Multiterminal Cuts
• Multicut on graphs of bounded clique-width
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• Quick separation in chordal and split graphs
• Multi-multiway cut problem on graphs of bounded branch width
• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• The treewidth of line graphs
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Constant factor approximation for tracking paths and fault tolerant feedback vertex set
• Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• Restricted vertex multicut on permutation graphs
• Multicuts in unweighted digraphs with bounded degree and bounded tree-width
• Simple and improved parameterized algorithms for multiterminal cuts
• Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
• A simple algorithm for multicuts in planar graphs with outer terminals
• Solution methods for the vertex variant of the network system vulnerability analysis problem
• Constant factor approximation for tracking paths and fault tolerant feedback vertex set
• The parameterised complexity of list problems on graphs of bounded treewidth
• How to Cut a Graph into Many Pieces
• Brief announcement: Bounded-degree cut is fixed-parameter tractable
• scientific article; zbMATH DE number 1187148 (Why is no real title available?)
• A logical approach to multicut problems
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• The critical node detection problem in networks: a survey
• Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions

This page was built for publication: Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width

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