Parallel algorithms for treewidth two
Babette de Fluiter1 
and Hans L. Bodlaender2
| (1) |
Centre for Quantitative Methods, P.O. Box 414, 5600 AK Eindhoven, the Netherlands |
| (2) |
Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, the Netherlands |
Abstract
In this paper we present a parallel algorithm that decides whether a graph G has treewidth at most two, and if so, constructs a tree decomposition or path decomposition of minimum width of G. The algorithm uses O(n) operations and O(log n log* n) time on an EREW PRAM, or O(log n) time on a CRCW PRAM. The algorithm makes use of the resemblance between series-parallel graphs and partial two-trees. It is a (non-trivial) extension of the parallel algorithm for series-parallel graphs that is presented in [6].
This research was carried out while the first author was working at the Department of Computer Science at Utrecht University, with support by the Foundation for Computer Science (S.I.O.N) of the Netherlands Organization for Scientific Research (N.W.O.). This research was partially supported by ESPRIT Long Term Research Project 20244 (project ALCOM IT: Algorithms and Complexity in Information Technology).
References secured to subscribers.