Loading...
Please wait, while we are loading the content...
Similar Documents
Parallel algorithms for series parallel graphs (1997)
| Content Provider | CiteSeerX |
|---|---|
| Author | Fluiter, Babette De Bodlaender, Hans L. |
| 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 jE j log jE j) time and O(jE j) operations on an EREW PRAM, and O(log jE j) time and O(jE j) operations on a CRCW PRAM (note that if G is a simple series parallel graph, then jE j = O(jV j)). With the same time and processor resources, a tree-decomposition of width at most two can be built of a given series parallel graph, and hence, very efficient parallel algorithms can be found for a large number of graph problems on series parallel graphs, including many well known problems, e.g., all problems that can be stated in monadic second order logic. The results hold for undirected series parallel graphs graphs, as well as for directed series parallel graphs. 1 |
| File Format | |
| Journal | Metabolic Engineering |
| Publisher Date | 1997-01-01 |
| Access Restriction | Open |
| Subject Keyword | Log Je Log Je Undirected Series Parallel Graph Graph Parallel Composition Rule Erew Pram Log Je Processor Resource Algorithm Us Decomposition Tree Parallel Algorithm Directed Series Parallel Graph Simple Series Parallel Graph Efficient Parallel Algorithm Crcw Pram Monadic Second Order Logic Graph Problem Series Parallel Graph |
| Content Type | Text |
| Resource Type | Article |
