Parallel Algorithms for the Split Decomposition
| dc.contributor.author | Novick, Mark B. | en_US |
| dc.date.accessioned | 2007-04-23T17:41:06Z | |
| dc.date.available | 2007-04-23T17:41:06Z | |
| dc.date.issued | 1989-12 | en_US |
| dc.description.abstract | We give a new $O(n^{2})$ time algorithm for finding Cunningham's split decomposition of an arbitrary undirected graph. We can convert this algorithm to an $NC$ algorithm that uses only $O(n^{3})$ processors. The related composition operation is a generalization of the modular (also called substitution of X-join) composition. The split decomposition is useful in recognizing special classes of graphs, such as circle graphs, which are the intersection graphs of arcs of a circle, and parity graphs, because these graphs are closed under the inverse composition operation. The decomposition can also be used to find $NC$ algorithms for some optimization problems on special families of graphs, assuming these problems can be solved in $NC$ for the indecomposable graphs of the decomposition. A new data structure, which we call a generalized $PQ$-tree, is used to make the algorithm efficient. Generalized $PQ$-trees make it easy to find sets that trivially intersect (one set is contained in the other or they are disjoint) each other. All the calculations on these trees can be done efficiently. Two other important parts of the algorithm are finding a breadth-first search tree and performing a modular decomposition of a graph. These computations are the bottlenecks to an efficient parallel algorithm since they are the only parts of the algorithm where $\omega (n^{2})$ processors are required. However, they can be performed in $O(n^{2})$ time sequentially. | en_US |
| dc.format.extent | 1472499 bytes | |
| dc.format.extent | 429882 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1075 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6874 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Parallel Algorithms for the Split Decomposition | en_US |
| dc.type | technical report | en_US |