Fast Parallel Reordering and Isomorphism Testing of k -Trees |
| |
Authors: | Del Greco Sekharan Sridhar |
| |
Affiliation: | Department of Mathematical and Computer Sciences, Loyola University Chicago, 6525 N. Sheridan Road, Chicago, IL 60626, USA., US School of Computer Science, University of Oklahoma, 200 Felgar Street, Norman, OK 73019, USA., US
|
| |
Abstract: | In this paper two problems on the class of k -trees, a subclass of the class of chordal graphs, are considered: the fast reordering problem and the isomorphism problem. An O(log 2 n) time parallel algorithm for the fast reordering problem is described that uses O(nk(n-k)/kern -1ptlog n) processors on a CRCW PRAM proving membership in the class NC for fixed k . An O(nk(k+1)!) time sequential algorithm for the isomorphism problem is obtained representing an improvement over the O(n 2 k(k+1)!) algorithm of Sekharan (the second author) [10]. A parallel version of this sequential algorithm is presented that runs in O(log 2 n) time using O((nk((k+1)!+n-k))/log n) processors improving on a parallel algorithm of Sekharan for the isomorphism problem [10]. Both the sequential and parallel algorithms use a concept introduced in this paper called the kernel of a k -tree. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|