Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
From MaRDI portal
Publication:4458884
DOI10.1016/S0196-6774(03)00073-7zbMath1079.68069MaRDI QIDQ4458884
Gruia Călinescu, Cristina G. Fernandes, Bruce A. Reed
Publication date: 14 March 2004
Published in: Journal of Algorithms (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ A logical approach to multicut problems ⋮ Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs ⋮ Algorithms for Multiterminal Cuts ⋮ Unnamed Item ⋮ Restricted vertex multicut on permutation graphs ⋮ Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ On the complexity of the multicut problem in bounded tree-width graphs and digraphs ⋮ How to Cut a Graph into Many Pieces ⋮ The critical node detection problem in networks: a survey ⋮ Disjoint paths in sparse graphs ⋮ Solution methods for the vertex variant of the network system vulnerability analysis problem ⋮ Simple and improved parameterized algorithms for multiterminal cuts ⋮ On the hardness of finding near-optimal multicuts in directed acyclic graphs ⋮ The treewidth of line graphs ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Quick separation in chordal and split graphs ⋮ A simple algorithm for multicuts in planar graphs with outer terminals
