ISSN:
1436-4646
Keywords:
Disjoint paths
;
Joins
;
Packing cuts
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Seymour (1981) proved that the cut criterion is necessary and sufficient for the solvability of the edge-disjoint paths problem when the union of the supply graph and the demand graph is planar and Eulerian. When only planarity is required, Middendorf and Pfeiffer (1993) proved the problem to be NP-complete. For this case, Korach and Penn (1992) proved that the cut criterion is sufficient for the existence of a near-complete packing of paths. Here we generalize this result by showing how a natural strengthening of the cut criterion yields better packings of paths. Analogously to Seymour's approach, we actually prove a theorem on packing cuts in an arbitrary graph and then the planar edge-disjoint paths case is obtained by planar dualization. The main result is derived from a theorem of Sebő (1990) on the structure of ±1 weightings of a bipartite graph with no negative circuits.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01585937
Permalink
