Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
From MaRDI portal
Publication:1942273
DOI10.1007/s10107-011-0506-7zbMath1263.90075MaRDI QIDQ1942273
Publication date: 18 March 2013
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-011-0506-7
Related Items
Discrete Convex Functions on Graphs and Their Algorithmic Applications, Discrete convexity and polynomial solvability in minimum 0-extension problems, Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity, Tree metrics and edge-disjoint \(S\)-paths, L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem, A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem, Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation, An Algorithm for Finding a Representation of a Subtree Distance
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On duality and fractionality of multicommodity flows in directed networks
- Extension of uniformly continuous transformations and hyperconvex metric spaces
- Tight spans of distances and the dual fractionality of undirected multiflow problems
- Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
- Über die Maximalzahl kantendisjunkter A-Wege
- Über die Maximalzahl kreuzungsfreier H-Wege
- Discrete convex analysis
- Metrics with finite sets of primitive extensions
- Minimum cost multiflows in undirected networks
- Multiflows and disjoint paths of minimum total cost
- Minimum 0-extensions of graph metrics
- Network flow, transportation and scheduling. Theory and algorithms
- Min-cost multiflows in node-capacitated undirected networks
- Graphs of some CAT(0) complexes
- Characterization of the distance between subtrees of a tree by the associated tight span
- A geometric study of the split decomposition
- Six theorems about injective metric spaces
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- On locating path- or tree-shaped facilities on networks
- Folder Complexes and Multiflow Combinatorial Dualities
- A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
- Some new results on node-capacitated packing of A-paths
- State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
- The optimal location of a path or tree in a tree network
- Graph minors. II. Algorithmic aspects of tree-width
- The generalized P‐forest problem on a tree network
- On some connectivity properties of Eulerian graphs
- Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
- Discrete Convex Analysis
- Multiway cuts in node weighted graphs
