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)

Full work available at URL https://doi.org/10.1016/S0196-6774(03)00073-7

zbMATH Keywords

Approximation algorithmsMulticutPolynomial-time approximation schemesTree-width

Mathematics Subject Classification ID

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

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

(28)

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

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)