Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two
1 |
| |
| Authors: | H L Bodlaender B van Antwerpen - de Fluiter |
| |
| Affiliation: | (1) This research was carried out while the second author was working at the Department of Computer Science of 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\/$). , NL;(2) Altera Corp., 101 Innovation Drive, San Jose, CA 95134, USA. babette\_van\_antwerpen@hotmail.com., US |
| |
| Abstract: | In this paper a parallel algorithm is given that, given a graph G=(V,E) , decides whether G is a series parallel graph, and, if so, builds a decomposition tree for G of series and parallel composition rules. The algorithm uses O(log \kern -1pt |E|log ^\ast \kern -1pt |E|) time and O(|E|) operations on an EREW PRAM, and O(log \kern -1pt |E|) time and O(|E|) operations on a CRCW PRAM. The results hold for undirected as well as for directed graphs.
Algorithms with the same resource bounds are described for the recognition of graphs of treewidth two, and for constructing
tree decompositions of treewidth two. Hence efficient parallel algorithms can be found for a large number of graph problems
on series parallel graphs and graphs with treewidth two. These include many well-known problems like all problems that can
be stated in monadic second-order logic.
Received July 15, 1997; revised January 29, 1999, and June 23, 1999. |
| |
| Keywords: | , Graph algorithms, Parallel algorithms, Treewidth, Series parallel graphs, Partial k -trees, |
| 本文献已被 SpringerLink 等数据库收录！ |
|
