Primal-dual approximation algorithms for integral flow and multicut in trees
From MaRDI portal
Publication:679443
DOI10.1007/BF02523685zbMATH Open0873.68075MaRDI QIDQ679443FDOQ679443
Authors: Vijay V. Vazirani, Mihalis Yannakakis, Naveen Garg 
Publication date: 28 May 1997
Published in: Algorithmica (Search for Journal in Brave)
Recommendations
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)
Cites Work
- Optimization, approximation, and complexity classes
- An Algorithm for Determining Whether a Given Binary Matroid is Graphic
- Graph minors. XIII: The disjoint paths problem
- The Complexity of Multiterminal Cuts
- A General Approximation Technique for Constrained Forest Problems
- A linear-time approximation algorithm for the weighted vertex cover problem
- Title not available (Why is that?)
- On the Complexity of Timetable and Multicommodity Flow Problems
- Title not available (Why is that?)
- On the hardness of approximating minimization problems
- Title not available (Why is that?)
- On the multiway cut polyhedron
- Approximate max-flow min-(multi)cut theorems and their applications
- Efficient probabilistically checkable proofs and applications to approximations
- Über die Maximalzahl kantendisjunkter A-Wege
- Title not available (Why is that?)
- An Almost Linear-Time Algorithm for Graph Realization
- On some connectivity properties of Eulerian graphs
- Tight integral duality gap in the Chinese postman problem
- A primal-dual approximation algorithm for generalized Steiner network problems
Cited In (only showing first 100 items - show all)
- Parameterized maximum path coloring
- Approximability of sparse integer programs
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
- Correlation clustering in general weighted graphs
- Finding edge-disjoint paths in networks: an ant colony optimization algorithm
- Selected Topics in Critical Element Detection
- Parameterized complexity of weighted multicut in trees
- A derandomized approximation algorithm for the critical node detection problem
- Parameterized complexity of multicut in weighted trees
- Improved parameterized and exact algorithms for cut problems on trees
- Path hitting in acyclic graphs
- Minimal multicut and maximal integer multiflow: a survey
- A primal-dual algorithm for weighted abstract cut packing
- Parameterized graph separation problems
- Complexity of the critical node problem over trees
- An approximation algorithm for the generalized \(k\)-multicut problem
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
- Designing WDM optical networks using branch-and-price
- On the hardness of finding near-optimal multicuts in directed acyclic graphs
- Call control with \(k\) rejections
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- Multicut in trees viewed through the eyes of vertex cover
- Evader interdiction: algorithms, complexity and collateral damage
- Restricted vertex multicut on permutation graphs
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- A greedy algorithm for multicut and integral multiflow in rooted trees
- Walrasian equilibrium: Hardness, approximations and tractable instances
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
- Line planning, path constrained network flow and inapproximability
- Path problems in generalized stars, complete graphs, and brick wall graphs
- On complexity, representation and approximation of integral multicommodity flows
- Approximation algorithms for feasible cut and multicut problems
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- Cardinality constrained and multicriteria (multi)cut problems
- Tree metrics and edge-disjoint \(S\)-paths
- Multicuts and integral multiflows in rings
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- On the advantage of overlapping clusters for minimizing conductance
- Clustering with qualitative information
- A randomized algorithm with local search for containment of pandemic disease spread
- Approximation Algorithms for k-Hurdle Problems
- A unified approach to approximating partial covering problems
- Improved algorithms for the multicut and multiflow problems in rooted trees
- A logarithmic approximation for unsplittable flow on line graphs
- Approximation algorithms for \(k\)-hurdle problems
- Finding disjoint paths with related path costs
- Half-integrality, LP-branching, and FPT algorithms
- Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
- How to Cut a Graph into Many Pieces
- Title not available (Why is that?)
- Constant-time local computation algorithms
- The maximum integer multiterminal flow problem in directed graphs
- Approximation and Online Algorithms
- The checkpoint problem
- A logical approach to multicut problems
- Cut problems in graphs with a budget constraint
- Partial multicuts in trees
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Parameterized complexity and approximation issues for the colorful components problems
- Covering problems in edge- and node-weighted graphs
- Multicommodity flows in tree-like networks
- The bi-objective critical node detection problem
- The critical node detection problem in networks: a survey
- Multiway cut and integer flow problems in trees
- Title not available (Why is that?)
- Approximation and hardness results for label cut and related problems
- Multicommodity flow in trees: packing via covering and iterated relaxation
- Exact algorithms and applications for tree-like Weighted Set Cover
- Routing in undirected graphs with constant congestion
- Routing concurrent video signals over SDH networks
- An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
- Grundy Distinguishes Treewidth from Pathwidth
- Hierarchical \(b\)-matching
- A note on multiflows and treewidth
- Vertex covering by paths on trees with its applications in machine translation
- Query-competitive algorithms for cheapest set problems under uncertainty
- Title not available (Why is that?)
- Approximating maximum integral multiflows on bounded genus graphs
- Disjoint paths in sparse graphs
- A preemptive algorithm for maximizing disjoint paths on trees
- Solving the edge‐disjoint paths problem using a two‐stage method
- Wavelength assignment in multifiber star networks
- Title not available (Why is that?)
- An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees
- Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
- Primal-dual approximation algorithms for feedback problems in planar graphs
- An FPT algorithm for planar multicuts with sources and sinks on the outer face
- Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
- Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time
- Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
- Critical node/edge detection problems on trees
- Title not available (Why is that?)
- On structural parameterizations of the edge disjoint paths problem
- Online interval scheduling with predictions
- A Preemptive Algorithm for Maximizing Disjoint Paths on Trees
- A survey of parameterized algorithms and the complexity of edge modification
- A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals
- Maximum edge-disjoint paths in planar graphs with congestion 2
- Multicuts in planar and bounded-genus graphs with bounded number of terminals
This page was built for publication: Primal-dual approximation algorithms for integral flow and multicut in trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679443)
