The Steiner k-Cut Problem

DOI10.1137/S0895480104445095MaRDI QIDQ5470831zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Sudipto Guha, Joseph (Seffi) Naor

Publication date 1 June 2006

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480104445095

zbMATH Keywords

\(k\)-cutapproximation algorithmlinear programminimum cutmultiway cutSteiner tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 2038710
• Approximation Algorithms for Steiner and Directed Multicuts
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Approximation algorithms for minimum \(K\)-cut
• scientific article; zbMATH DE number 1775387

Cited in

(17)

• Beating the 2-approximation factor for global bicut
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• The vertex \(k\)-cut problem
• Designing FPT algorithms for cut problems using randomized contractions
• LP relaxation and tree packing for minimum k-cut
• The Fermat-Steiner Problem
• scientific article; zbMATH DE number 2038710 (Why is no real title available?)
• Multi-budgeted directed cuts
• Fast and deterministic approximations for \(k\)-cut
• Fast and Deterministic Approximations for k-Cut.
• Approximating Requirement Cut via a Configuration LP
• Multiway cuts with a choice of representatives
• Exponential-time approximation schemes via compression
• Approximating submodular matroid-constrained partitioning
• Multi-budgeted directed cuts
• Approximation algorithms for requirement cut on graphs
• An improved approximation algorithm for requirement cut

This page was built for publication: The Steiner k-Cut Problem

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