NC Algorithms for Recognizing Partial 2-Trees and 3-Trees
Daniel Granot, Darko Skorin‐Kapov · SIAM Journal on Discrete Mathematics · 1991
The existence of a k-separator in a partial k-tree graph is proved and a linear time algorithm is constructed that finds such a separator in k-trees. This algorithm can be used to obtain a balanced binary decomposition of a k-tree in $O( n\log n )$ time. Some other separation properties of partial k-trees are derived and used to construct a balanced decomposition of an embedding of a k-connected partial k-tree when $k = 2,3$. Finally, NC algorithms are constructed for the recognition of a partial k-tree for $k = 2,3$. For $k = 2$ and $k = 3$ these algorithms run in $O( \log^{2} n )$ time using, respectively, $O( n^3 )$ and $O( {n^4 } )$ processors. Thus, the algorithms for $k = 2,3$ improve considerably the processor bound of Chandrasekharan and Hedetniemi [Proceedings of the 26th Annual Allerton Conference on Communication, Control and Computing, 1989, pp. 283–292] general algorithm for the parallel recognition of partial k-trees that would require $O( \log n )$ time and, respectively, $O( n^{10} )$ and $O( n^{12} )$ processors in these cases.