×

Efficient algorithms for minimal disjoint path problems on chordal graphs. (English) Zbl 0845.05084

Summary: Disjoint paths have applications in establishing bottleneck-free communication between processors in a network. The problem of finding minimum delay disjoint paths in a network directly reduces to the problem of finding the minimal disjoint paths in the graph which models the network. Previous results for this problem on chordal graphs were an \(O ( |V |\cdot |E |^2)\) algorithm for 2 edge disjoint paths and an \(O (|V |\cdot |E |)\) algorithm for 2 vertex disjoint paths. In this paper, we give an \(O (|V |\cdot|E |)\) algorithm for 2 vertex disjoint paths and an \(O (|V |+ |E |) \) algorithm for 2 edge disjoint paths, which is a significant improvement over the previous result.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI Link