Primal-dual approximation algorithms for integral flow and multicut in trees
From MaRDI portal
(Redirected from Publication:679443)
Recommendations
Cites work
- scientific article; zbMATH DE number 3876616 (Why is no real title available?)
- scientific article; zbMATH DE number 16298 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 3314878 (Why is no real title available?)
- A General Approximation Technique for Constrained Forest Problems
- A linear-time approximation algorithm for the weighted vertex cover problem
- A primal-dual approximation algorithm for generalized Steiner network problems
- An Algorithm for Determining Whether a Given Binary Matroid is Graphic
- An Almost Linear-Time Algorithm for Graph Realization
- Approximate max-flow min-(multi)cut theorems and their applications
- Efficient probabilistically checkable proofs and applications to approximations
- Graph minors. XIII: The disjoint paths problem
- On some connectivity properties of Eulerian graphs
- On the Complexity of Timetable and Multicommodity Flow Problems
- On the hardness of approximating minimization problems
- On the multiway cut polyhedron
- Optimization, approximation, and complexity classes
- The Complexity of Multiterminal Cuts
- Tight integral duality gap in the Chinese postman problem
- Über die Maximalzahl kantendisjunkter A-Wege
Cited in
(only showing first 100 items - show all)- A tight relation between series-parallel graphs and bipartite distance hereditary graphs
- The connected critical node problem
- How to Cut a Graph into Many Pieces
- A fixed-parameter tractability result for multicommodity demand flow in trees
- scientific article; zbMATH DE number 6861995 (Why is no real title available?)
- New results on planar and directed multicuts
- Kernels for the disjoint paths problem on subclasses of chordal graphs
- Constant factor approximation algorithm for weighted flow-time on a single machine in pseudopolynomial time
- Constant-time local computation algorithms
- Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
- The maximum integer multiterminal flow problem in directed graphs
- Multicut Is FPT
- On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths
- The checkpoint problem
- Improved algorithms for scheduling unsplittable flows on paths
- Max-multiflow/min-multicut for G+H series-parallel
- Approximation and Online Algorithms
- A logical approach to multicut problems
- Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity
- Partial multicuts in trees
- scientific article; zbMATH DE number 7559431 (Why is no real title available?)
- Cut problems in graphs with a budget constraint
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Multicommodity flows in tree-like networks
- A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
- A simple rounding scheme for multistage optimization
- The bi-objective critical node detection problem
- Almost polynomial hardness of node-disjoint paths in grids
- The critical node detection problem in networks: a survey
- An approximation algorithm for the k-prize-collecting multicut on a tree problem
- Multiway cut and integer flow problems in trees
- Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
- Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time
- Kernels for the disjoint paths problem on subclasses of chordal graphs
- Integer plane multiflow maximisation: one-quarter-approximation and gaps
- On the generalized multiway cut in trees problem
- scientific article; zbMATH DE number 2038727 (Why is no real title available?)
- Approximation and hardness results for label cut and related problems
- Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
- Multicommodity flow in trees: packing via covering and iterated relaxation
- Packing cycles in planar and bounded-genus graphs
- Exact algorithms and applications for tree-like Weighted Set Cover
- Parameterized maximum path coloring
- Approximability of sparse integer programs
- Routing in undirected graphs with constant congestion
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- scientific article; zbMATH DE number 7278041 (Why is no real title available?)
- Routing concurrent video signals over SDH networks
- Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
- The B-prize-collecting multicut problem in paths, spider graphs and rings
- An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
- 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
- Correlation clustering in general weighted graphs
- Grundy Distinguishes Treewidth from Pathwidth
- Designing FPT algorithms for cut problems using randomized contractions
- Disjoint paths in sparse graphs
- A preemptive algorithm for maximizing disjoint paths on trees
- Finding edge-disjoint paths in networks: an ant colony optimization algorithm
- Approximating maximum integral multiflows on bounded genus graphs
- A derandomized approximation algorithm for the critical node detection problem
- Improved parameterized and exact algorithms for cut problems on trees
- Path hitting in acyclic graphs
- Minimal multicut and maximal integer multiflow: a survey
- Parameterized complexity of weighted multicut in trees
- Parameterized complexity of multicut in weighted trees
- Solving the edge‐disjoint paths problem using a two‐stage method
- Parameterized graph separation problems
- A primal-dual algorithm for weighted abstract cut packing
- Complexity of the critical node problem over trees
- Wavelength assignment in multifiber star networks
- The parameterized complexity landscape of the unsplittable flow problem
- An approximation algorithm for the generalized k-multicut problem
- Approximating maximum integral multiflows on bounded genus graphs
- Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
- An approximation algorithm for the B-prize-collecting multicut problem in trees
- Designing WDM optical networks using branch-and-price
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
- Primal-dual approximation algorithms for feedback problems in planar graphs
- An FPT algorithm for planar multicuts with sources and sinks on the outer face
- On the hardness of finding near-optimal multicuts in directed acyclic graphs
- Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
- Call control with \(k\) rejections
- Multicut in trees viewed through the eyes of vertex cover
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
- Evader interdiction: algorithms, complexity and collateral damage
- Restricted vertex multicut on permutation graphs
- On structural parameterizations of the edge disjoint paths problem
- scientific article; zbMATH DE number 7278054 (Why is no real title available?)
- A greedy algorithm for multicut and integral multiflow in rooted trees
- Walrasian equilibrium: Hardness, approximations and tractable instances
- Critical node/edge detection problems on trees
- A Preemptive Algorithm for Maximizing Disjoint Paths on Trees
- Online interval scheduling with predictions
- All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
- Line planning, path constrained network flow and inapproximability
- Path problems in generalized stars, complete graphs, and brick wall graphs
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)
