A NOTE ON PACKING PATHS IN PLANAR GRAPHS

Authors
Citation
A. Frank et Z. Szigeti, A NOTE ON PACKING PATHS IN PLANAR GRAPHS, Mathematical programming, 70(2), 1995, pp. 201-209
Citations number
7
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
ISSN journal
00255610
Volume
70
Issue
2
Year of publication
1995
Pages
201 - 209
Database
ISI
SICI code
0025-5610(1995)70:2<201:ANOPPI>2.0.ZU;2-M
Abstract
Seymour (1981)proved that the cut criterion is necessary and sufficien t for the solvability of the edge-disjoint paths problem when the unio n of the supply graph and the demand graph is planar and Eulerian. Whe n only planarity is required, Middendorf and Pfeiffer (1993) proved th e problem to be NP-complete, For this case, Korach and Penn (1992) pro ved that the cut criterion is sufficient for the existence of a near-c omplete packing of paths. Here we generalize this result by showing ho w a natural strengthening of the cut criterion yields better packings of paths. Analogously to Seymour's approach, we actually prove a theor em on packing cuts in an arbitrary graph and then the planar edge-disj oint paths case is obtained by planar dualization, The main result is derived from a theorem of Sebo (1990) on the structure of +/- 1 weight ings of a bipartite graph with no negative circuits.