Abstract | ||
---|---|---|
An efficient reduction process for path problems on circular-arc graphs is introduced. For the parity path problem, this reduction gives anO(n+m) algorithm for proper circular-arc graphs, and anO(n+m) algorithm for general circular-arc graphs. This reduction also gives anO(n+m) algorithm for the two path problem on circular-arc graphs. |
Year | DOI | Venue |
---|---|---|
1991 | 10.1007/BF01931279 | BIT |
Keywords | Field | DocType |
efficient reduction,path problem,circular-arc graph | Discrete mathematics,Combinatorics,Indifference graph,Mathematical optimization,Induced path,Chordal graph,Hamiltonian path problem,Shortest Path Faster Algorithm,Pathwidth,Longest path problem,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
31 | 2 | 0006-3835 |
Citations | PageRank | References |
7 | 0.68 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Srinivasa R. Arikati | 1 | 87 | 7.78 |
C. Pandu Rangan | 2 | 1434 | 149.57 |
Glenn K. Manacher | 3 | 205 | 98.95 |