Efficient algorithms for minimal disjoint path problems on chordal graphs
C.P. Gopalakrishnan; C.R. Satyan; C. Pandu Rangan
Discussiones Mathematicae Graph Theory (1995)
- Volume: 15, Issue: 2, page 119-145
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topC.P. Gopalakrishnan, C.R. Satyan, and C. Pandu Rangan. "Efficient algorithms for minimal disjoint path problems on chordal graphs." Discussiones Mathematicae Graph Theory 15.2 (1995): 119-145. <http://eudml.org/doc/270438>.
@article{C1995,
abstract = {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| |E|²) algorithm for 2 edge disjoint paths and an O(|V| |E|) algorithm for 2 vertex disjoint paths. In this paper, we give an O(|V| |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.},
author = {C.P. Gopalakrishnan, C.R. Satyan, C. Pandu Rangan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {chordal graph; minimal paths; disjoint paths; clique; bfs; network; chordal graphs; algorithm},
language = {eng},
number = {2},
pages = {119-145},
title = {Efficient algorithms for minimal disjoint path problems on chordal graphs},
url = {http://eudml.org/doc/270438},
volume = {15},
year = {1995},
}
TY - JOUR
AU - C.P. Gopalakrishnan
AU - C.R. Satyan
AU - C. Pandu Rangan
TI - Efficient algorithms for minimal disjoint path problems on chordal graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 2
SP - 119
EP - 145
AB - 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| |E|²) algorithm for 2 edge disjoint paths and an O(|V| |E|) algorithm for 2 vertex disjoint paths. In this paper, we give an O(|V| |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.
LA - eng
KW - chordal graph; minimal paths; disjoint paths; clique; bfs; network; chordal graphs; algorithm
UR - http://eudml.org/doc/270438
ER -
References
top- [G 80] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, 1980).
- [K 75] R.M. Karp, On the computational complexity of combinatorial problems, Networks 5 (1975) 45-68. Zbl0324.05003
- [O 80] T. Ohtsuki, The two disjoint path problem and wire routing design, in: Proc. of the 17th Symp. of Res. Inst. of Electrical Comm. (1980) 257-267.
- [PS 78] Y. Perl, Y. Shiloach, Finding two disjoint paths between two pairs of vertices in a graph, J. of the ACM 25 (1978) 1-9, doi: 10.1145/322047.322048. Zbl0365.68026
- [RS 86] N. Robertson, P.D. Seymour, Graph minors XIII. The disjoint paths problem, Manuscript 1986.
- [S 80] Y. Shiloach, A polynomial solution to the undirected two paths problem, J. of the ACM 27 (1980) 445-456, doi: 10.1145/322203.322207. Zbl0475.68042
- [S 89] A. Schwill, Shortest edge-disjoint paths in graphs, in: Proc. of the 6th STACS (1989) 505-516.
- [S 90] A. Schwill, Nonblocking graphs: Greedy algorithms to compute disjoint paths, in: Proc. of the 7th STACS (1990) 250-262.
- [KPS 91] S.V. Krishnan, C. Pandu Rangan, S. Seshadri, A. Schwill, Two Disjoint Paths in Chordal graphs, Technical report, 2/91, February 1991, University of Oldenburg, Germany.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.