Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!ames!sparkyfs.erg.sri.com!vlad
From: vlad@erg.sri.com (beyer)
Newsgroups: comp.theory
Subject: Re: 2-pair edge-disjoint paths of minimum length
Message-ID: <1991Feb15.103309.8031@erg.sri.com>
Date: 15 Feb 91 10:33:09 GMT
References: <1991Feb14.205827.21461@cs.umn.edu>
Sender: news@erg.sri.com
Distribution: usa
Organization: SRI International, Menlo Park, CA
Lines: 18

In article <1991Feb14.205827.21461@cs.umn.edu> chingtin@umn-cs.cs.umn.edu (Chingting Wu) writes:
>
>
>Given a planar graph G=<V,E>, and four vertex s1,s2,t1,t2 in V, and integer K,
>Is there a polynomial time algorithm to find two edge-disjoint paths (s1-- t1) 
>(s2--t2), whose total length is less than K edges (or whose total length is 
>minimized)?  I would like to have a reference on this problem or any
>generalization of it.
>
>
>Thanks a lot.
>
>Chingting Wu

This is a two-commodity flow problem that has a lot of references.
How about Tarjan's book on Network Flows?

Vlad