vlad@erg.sri.com (beyer) (02/15/91)
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