We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Parallel Algorithms for Hamiltonian 2-Separator Chordal Graphs.
- Authors
Panda, B. S.; Natarajan, Vijay; Das, Sajal K.; Akl, S.
- Abstract
In this paper we propose a parallel algorithm to construct a one-sided monotone polygon from a Hamiltonian 2-separator chordal graph. The algorithm requires O(log n) time and O(n) processors on the CREW PRAM model, where n is the number of vertices and m is the number of edges in the graph. We also propose parallel algorithms to recognize Hamiltonian 2-separator chordal graphs and to construct a Hamiltonian cycle in such a graph. They run in O(log² n) time using O(mn) processors on the CRCW PRAM model and O(log² n) time using O(m) processors on the CREW PRAM model, respectively.
- Subjects
PARALLEL algorithms; HAMILTONIAN systems; MONOTONE operators
- Publication
Parallel Processing Letters, 2002, Vol 12, Issue 1, p51
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626402000823