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

DOI10.1016/S0196-6774(03)00073-7zbMATH Open1079.68069MaRDI QIDQ4458884FDOQ4458884

Gruia Calinescu, Bruce Reed, Cristina G. Fernandes

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)

Cited In (24)

• Disjoint paths in sparse graphs
• Algorithms for Multiterminal Cuts
• Quick separation in chordal and split graphs
• 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
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• 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
• Title not available (Why is that?)
• Multicuts in planar and bounded-genus graphs with bounded number of terminals
• Simple and improved parameterized algorithms for multiterminal cuts
• 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
• A simple algorithm for multicuts in planar graphs with outer terminals
• 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
• Title not available (Why is that?)
• 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)