Tight spans of distances and the dual fractionality of undirected multiflow problems

DOI10.1016/J.JCTB.2009.03.001zbMATH Open1190.05057OpenAlexW2123783074MaRDI QIDQ1044206FDOQ1044206

Authors: Hiroshi Hirai 

Publication date: 11 December 2009

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/126567

Recommendations

• On duality and fractionality of multicommodity flows in directed networks
• The maximum multiflow problems with bounded fractionality
• \(T_X\)-approaches to multiflows and metrics
• The maximum multiflow problems with bounded fractionality
• On one maximum multiflow problem and related metrics

zbMATH Keywords

polyhedral combinatoricsmetricsmulticommodity flowstight spans

Mathematics Subject Classification ID

Distance in graphs (05C12) Flows in graphs (05C21)

Cites Work

• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Tropical convexity
• Lectures on Polytopes
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graphs of some CAT(0) complexes
• Six theorems about injective metric spaces
• Geometry of cuts and metrics
• Title not available (Why is that?)
• Multi-Commodity Network Flows
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
• Title not available (Why is that?)
• Combinatorial approaches to multiflow problems
• Polyhedra related to undirected multicommodity flows
• Metrics with finite sets of primitive extensions
• Minimum 0-extensions of graph metrics
• On tight spans for directed distances
• Characterization of the distance between subtrees of a tree by the associated tight span
• Title not available (Why is that?)
• Generosity Helps or an 11-Competitive Algorithm for Three Servers
• On some connectivity properties of Eulerian graphs
• Hereditary modular graphs
• A \(T_X\)-approach to some results on cuts and metrics
• A characterization of minimizable metrics in the multifacility location problem
• Title not available (Why is that?)

Cited In (18)

• The maximum multiflow problems with bounded fractionality
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• Title not available (Why is that?)
• The maximum multiflow problems with bounded fractionality
• Bounded fractionality of the multiflow feasibility problem for demand graph \(K_3 + K_3\) and related maximization problems
• Tree metrics and edge-disjoint \(S\)-paths
• Minimum 0-extension problems on directed metrics
• On the fractionality of the path packing problem
• Metric packing for \(K_ 3 + K_ 3\)
• Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
• \(T_X\)-approaches to multiflows and metrics
• Folder complexes and multiflow combinatorial dualities
• On tight spans for directed distances
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• Optimal realizations of two-dimensional, totally-decomposable metrics
• On duality and fractionality of multicommodity flows in directed networks
• The polytopal structure of the tight-span of a totally split-decomposable metric
• On fractional multicommodity flows and distance functions

This page was built for publication: Tight spans of distances and the dual fractionality of undirected multiflow problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1044206)