TY - GEN
T1 - NC2 algorithms regarding Hamiltonian paths and circuits in interval graphs
AU - Liang, Y. Daniel
AU - Greenlaw, Raymond
AU - Manacher, Glenn
N1 - Publisher Copyright:
© 1994, Springer Verlag. All rights reserved.
PY - 1994
Y1 - 1994
N2 - This paper describes an O(log2 n) time, n processor EREW PRAM algorithm to determine if there is a Hamiltonian path in an interval graph. If there is a Hamiltonian path, we can find it within the same resource bounds. Many graph theoretic problems including finding all maximal cliques, optimal coloring, minimum clique cover, minimum weight dominating set, and maximum independent set were previously known to be in NC when restricted to interval graphs. However, the Hamiltonian path problem was open and resisted classification until now. We also show that testing whether an interval graph has a Hamiltonian circuit can be done in NC2. If the intervals are presorted, our parallel approach leads to an O(nα(n)) sequential algorithm, where α(n) is the inverse of Ackermann's function. This improves on the previous bound of O(n log log n) for the sequential case with presorted intervals.
AB - This paper describes an O(log2 n) time, n processor EREW PRAM algorithm to determine if there is a Hamiltonian path in an interval graph. If there is a Hamiltonian path, we can find it within the same resource bounds. Many graph theoretic problems including finding all maximal cliques, optimal coloring, minimum clique cover, minimum weight dominating set, and maximum independent set were previously known to be in NC when restricted to interval graphs. However, the Hamiltonian path problem was open and resisted classification until now. We also show that testing whether an interval graph has a Hamiltonian circuit can be done in NC2. If the intervals are presorted, our parallel approach leads to an O(nα(n)) sequential algorithm, where α(n) is the inverse of Ackermann's function. This improves on the previous bound of O(n log log n) for the sequential case with presorted intervals.
UR - http://www.scopus.com/inward/record.url?scp=85027404899&partnerID=8YFLogxK
U2 - 10.1007/3-540-58078-6_5
DO - 10.1007/3-540-58078-6_5
M3 - Conference article
AN - SCOPUS:85027404899
SN - 9783540580782
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 45
EP - 57
BT - Parallel and Distributed Computing
A2 - Cosnard, Michel
A2 - Ferreira, Afonso
A2 - Peters, Joseph
PB - Springer Verlag
T2 - 1st Canada-France Conference on Parallel and Distributed Computing, 1994
Y2 - 19 May 1994 through 21 May 1994
ER -