Gopalakrishnan, C. P.; Satyan, C. R.; Pandu Rangan, C. Efficient algorithms for minimal disjoint path problems on chordal graphs. (English) Zbl 0845.05084 Discuss. Math., Graph Theory 15, No. 2, 119-145 (1995). 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 Keywords:minimal paths; clique; disjoint paths; network; chordal graphs; algorithm PDFBibTeX XMLCite \textit{C. P. Gopalakrishnan} et al., Discuss. Math., Graph Theory 15, No. 2, 119--145 (1995; Zbl 0845.05084) Full Text: DOI Link