ISSN:
1432-0541
Keywords:
Modular decomposition
;
Substitution decomposition
;
Prime tree family
;
Graph decomposition
;
2-Structures
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract This paper gives anO(n 2) incremental algorithm for computing the modular decomposition of 2-structures [1], [2]. A 2-structure is a type of edge-colored graph, and its modular decomposition is also known as the prime tree family. Modular decomposition of 2-structures arises in the study of relational systems. The modular decomposition of undirected graphs and digraphs is a special case, and has applications in a number of combinatorial optimization problems. This algorithm generalizes elements of a previousO(n 2) algorithm of Muller and Spinrad [3] for the decomposition of undirected graphs. However, Muller and Spinrad's algorithm employs a sophisticated data structure that impedes its generalization to digraphs and 2-structures, and limits its practical use. We replace this data structure with a scheme that labels each edge with at most one node, thereby obtaining an algorithm that is both practical and general to 2-structures.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01206330
Permalink
