TY - GEN
T1 - An efficient nc algorithm for finding hamiltonian cycles in dense directed graphs
AU - Fürer, Martin
AU - Raghavachari, Balaji
N1 - Funding Information:
t This work was supported in part by the NSF under grant CCR-8805978.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1991.
PY - 1991
Y1 - 1991
N2 - Let G be a directed graph with n vertices such that whenever there is no arc from any vertex u to another vertex υ, then the sum of the outdegree of u and the indegree of ν is at least n. It is known that such a graph G always contains a Hamiltonian cycle. We show that such a cycle can be computed with a linear number of processors in O(log3 n) time on a CREW PRAM.
AB - Let G be a directed graph with n vertices such that whenever there is no arc from any vertex u to another vertex υ, then the sum of the outdegree of u and the indegree of ν is at least n. It is known that such a graph G always contains a Hamiltonian cycle. We show that such a cycle can be computed with a linear number of processors in O(log3 n) time on a CREW PRAM.
UR - http://www.scopus.com/inward/record.url?scp=85027609084&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85027609084&partnerID=8YFLogxK
U2 - 10.1007/3-540-54233-7_153
DO - 10.1007/3-540-54233-7_153
M3 - Conference contribution
AN - SCOPUS:85027609084
SN - 9783540542339
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 429
EP - 440
BT - Automata, Languages and Programming - 18th International Colloquium, Proceedings
A2 - Albert, Javier Leach
A2 - Artalejo, Mario Rodriguez
A2 - Monien, Burkhard
PB - Springer Verlag
T2 - 18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991
Y2 - 8 July 1991 through 12 July 1991
ER -