An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
✍ Scribed by A. Ehrenfeucht; H.N. Gabow; R.M. Mcconnell; S.J. Sullivan
- Publisher
- Elsevier Science
- Year
- 1994
- Tongue
- English
- Weight
- 526 KB
- Volume
- 16
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in (O\left(n^{2}\right)) time, when (n) is the number of nodes of the two-structure. A directed or undirected graph is a special case of a two-structure, and the restriction of the decomposition to graphs is known as the modular decomposition or substitution decomposition. The decomposition has applications in solving certain scheduling problems and a number of problems on graphs and partial orders. Two algorithms with a comparable time bound have previously been published for undirected graphs, but they make use of elaborate data structures that limit their practical use, and they have no easy generalization to directed graphs or two-structures. (1) 1994 Academic Press. Inc.