Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
type: Item
instance of: scholarly article
title: Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
zbMATH Open document ID: 1263.90075
author: Hiroshi Hirai
published in: Mathematical Programming. Series A. Series B
publication date: 2013-03-18T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6145981
zbMATH Keywords: multicommodity flows
zbMATH Keywords: half-integrality
zbMATH Keywords: tree-shaped facility locations
MaRDI profile type: Publication
full work available at URL: s10107-011-0506-7
OpenAlex ID: W2098047723
cites work: Extension of uniformly continuous transformations and hyperconvex metric spaces
cites work: A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
cites work: Min-cost multiflows in node-capacitated undirected networks
cites work: Graphs of some CAT(0) complexes
cites work: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
cites work: Multiway cuts in node weighted graphs
cites work: Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
cites work: On locating path- or tree-shaped facilities on networks
cites work: A geometric study of the split decomposition
cites work: Characterization of the distance between subtrees of a tree by the associated tight span
cites work: Tight spans of distances and the dual fractionality of undirected multiflow problems
cites work: Q2999654
cites work: Folder Complexes and Multiflow Combinatorial Dualities
cites work: On duality and fractionality of multicommodity flows in directed networks
cites work: Network flow, transportation and scheduling. Theory and algorithms
cites work: Six theorems about injective metric spaces
cites work: Minimum cost multiflows in undirected networks
cites work: Multiflows and disjoint paths of minimum total cost
cites work: Minimum 0-extensions of graph metrics
cites work: Metrics with finite sets of primitive extensions
cites work: On some connectivity properties of Eulerian graphs
cites work: Über die Maximalzahl kantendisjunkter A-Wege
cites work: Über die Maximalzahl kreuzungsfreier H-Wege
cites work: The optimal location of a path or tree in a tree network
cites work: Discrete convex analysis
cites work: Discrete Convex Analysis
cites work: Some new results on node-capacitated packing of A-paths
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Q3730336
cites work: The generalized P‐forest problem on a tree network
cites work: State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
cites work: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
cites work: Q4782696
DOI: 10.1007/S10107-011-0506-7
Recommended article: Improved complexity results for several multifacility location problems on trees
Recommended article: Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections
Recommended article: Distance-constrained multifacility minimax location problems on tree networks
Recommended article: Q3599805
Recommended article: The general facility location problem with connectivity on trees
Recommended article: Planar multifacility location problems with tree structure and finite dominating sets
Recommended article: Multiple allocation tree of hubs location problem for non-complete networks
Recommended article: On the approximation of the generalized capacitated tree-routing problem
Recommended article: Optimal algorithms for the path/tree-shaped facility location problems in trees
Recommended article: Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees
description: scientific article; zbMATH DE number 6145981