Name
Abstract | ||
|---|---|---|
We give some results on the existence of fractional and integral solutions to multicommodity flow problems, and on the related problem of decomposing distance functions into cuts. One of the results is: Let G = ( V , E ) be a planar bipartite graph. Then there exist subsets W 1 ,…, W t of V so that for each pair υ′, υ″ of vertices on the boundary of G , the distance of υ′ and υ″ in G is equal to the number of j = 1,…, t with |{ υ ′, υ ″} ⋂ W j | = 1 and so that the cuts δ ( W j ) are pairwise disjoint. |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1016/0012-365X(88)90137-9 | Discrete Mathematics |
Keywords | Field | DocType |
distance function,fractional multicommodity flow,multicommodity flow | Discrete mathematics,Combinatorics,Disjoint sets,Vertex (geometry),Bipartite graph,Planar,Multi-commodity flow problem,Mathematics | Journal |
Volume | Issue | ISSN |
73 | 1-2 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. A. J. Hurkens | 1 | 168 | 16.20 |
| A. Schrijver | 2 | 10 | 2.52 |
| Éva Tardos | 3 | 9299 | 963.85 |