Fast Parallel Reordering and Isomorphism Testing of k ‐Trees

Fast Parallel Reordering and Isomorphism Testing of k ‐Trees

0.00 Avg rating0 Votes
Article ID: iaor20121073
Volume: 32
Issue: 1
Start Page Number: 61
End Page Number: 72
Publication Date: Jan 2002
Journal: Algorithmica
Authors: , ,
Keywords: trees, chordal graphs
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.

Reviews

Required fields are marked *. Your email address will not be published.