Approximation algorithms for requirement cut on graphs

DOI10.1007/s00453-008-9171-5zbMath1215.05135OpenAlexW2138522610MaRDI QIDQ848961

Viswanath Nagarajan, R. Ravi

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9171-5

zbMATH Keywords

graph partitioningapproximation algorithmscut problems

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Approximating Requirement Cut via a Configuration LP ⋮ An improved approximation algorithm for requirement cut

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The multi-multiway cut problem
• An improved approximation algorithm of MULTIWAY CUT.
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• The geometry of graphs and some of its algorithmic applications
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Approximation Algorithms for Steiner and Directed Multicuts
• A threshold of ln n for approximating set cover
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Maximal Flow Through a Network
• The Complexity of Multiterminal Cuts
• Finding k Cuts within Twice the Optimal
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Approximation algorithms for the covering Steiner problem
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Euclidean distortion and the sparsest cut
• The Steiner k-Cut Problem
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Expander flows, geometric embeddings and graph partitioning
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Approximation algorithms for requirement cut on graphs