Primal-dual approximation algorithms for integral flow and multicut in trees
From MaRDI portal
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)- Tree metrics and edge-disjoint \(S\)-paths
- A unified approach to approximating partial covering problems
- Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
- A logarithmic approximation for unsplittable flow on line graphs
- Path hitting in acyclic graphs
- On the advantage of overlapping clusters for minimizing conductance
- On complexity, representation and approximation of integral multicommodity flows
- Approximation algorithms for \(k\)-hurdle problems
- Clustering with qualitative information
- Multicommodity flows in tree-like networks
- Parameterized maximum path coloring
- The critical node detection problem in networks: a survey
- Minimal multicut and maximal integer multiflow: a survey
- Walrasian equilibrium: Hardness, approximations and tractable instances
- Hierarchical \(b\)-matching
- Complexity of the critical node problem over trees
- The maximum integer multiterminal flow problem in directed graphs
- An approximation algorithm for the generalized \(k\)-multicut problem
- Improved algorithms for the multicut and multiflow problems in rooted trees
- The checkpoint problem
- Cut problems in graphs with a budget constraint
- Partial multicuts in trees
- Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
- Correlation clustering in general weighted graphs
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Evader interdiction: algorithms, complexity and collateral damage
- Multiway cut and integer flow problems in trees
- Approximation algorithms for feasible cut and multicut problems
- How to Cut a Graph into Many Pieces
- Restricted vertex multicut on permutation graphs
- Approximation and hardness results for label cut and related problems
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
- Approximability of sparse integer programs
- Line planning, path constrained network flow and inapproximability
- Multicuts and integral multiflows in rings
- Finding disjoint paths with related path costs
- The bi-objective critical node detection problem
- Parameterized complexity of weighted multicut in trees
- A derandomized approximation algorithm for the critical node detection problem
- scientific article; zbMATH DE number 6861995 (Why is no real title available?)
- On the hardness of finding near-optimal multicuts in directed acyclic graphs
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- A logical approach to multicut problems
- scientific article; zbMATH DE number 2038727 (Why is no real title available?)
- A primal-dual algorithm for weighted abstract cut packing
- Parameterized complexity of multicut in weighted trees
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- Designing FPT algorithms for cut problems using randomized contractions
- Selected topics in critical element detection
- Cardinality constrained and multicriteria (multi)cut problems
- Constant-time local computation algorithms
- Path problems in generalized stars, complete graphs, and brick wall graphs
- Half-integrality, LP-branching, and FPT algorithms
- Multicommodity flow in trees: packing via covering and iterated relaxation
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- A randomized algorithm with local search for containment of pandemic disease spread
- Exact algorithms and applications for tree-like Weighted Set Cover
- Improved parameterized and exact algorithms for cut problems on trees
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
- Designing WDM optical networks using branch-and-price
- Parameterized graph separation problems
- Multicut in trees viewed through the eyes of vertex cover
- Finding edge-disjoint paths in networks: an ant colony optimization algorithm
- Approximation and Online Algorithms
- A greedy algorithm for multicut and integral multiflow in rooted trees
- Approximation Algorithms for k-Hurdle Problems
- Call control with \(k\) rejections
- New results on planar and directed multicuts
- Almost polynomial hardness of node-disjoint paths in grids
- Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
- Multicut Is FPT
- Connected \(k\)-center and \(k\)-diameter clustering
- On the dominant of the multicut polytope
- Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
- Routing in undirected graphs with constant congestion
- Primal-dual approximation algorithms for a packing-covering pair of problems
- All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
- Constant factor approximation algorithm for weighted flow-time on a single machine in pseudopolynomial time
- Solution methods for the vertex variant of the network system vulnerability analysis problem
- Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
- Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time
- A note on multiflows and treewidth
- A fixed-parameter tractability result for multicommodity demand flow in trees
- Primal-dual approximation algorithms for feedback problems in planar graphs
- Maximum edge-disjoint paths in planar graphs with congestion 2
- Improved algorithms for scheduling unsplittable flows on paths
- Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
- Integer plane multiflow maximisation: one-quarter-approximation and gaps
- Critical node/edge detection problems on trees
- scientific article; zbMATH DE number 7278054 (Why is no real title available?)
- A simple algorithm for multicuts in planar graphs with outer terminals
- A tight relation between series-parallel graphs and bipartite distance hereditary graphs
- On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths
- On structural parameterizations of the edge disjoint paths problem
- Approximating maximum integral multiflows on bounded genus graphs
- A simple rounding scheme for multistage optimization
- The power of cut-based parameters for computing edge-disjoint paths
- An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties
- Vertex covering by paths on trees with its applications in machine translation
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)
