Loading...
Please wait, while we are loading the content...
Similar Documents
An o(n²) incremental algorithm for modular decomposition of graphs and 2-structures (1995).
| Content Provider | CiteSeerX |
|---|---|
| Author | Mcconnell, R. M. |
| Abstract | This paper gives an O(n²) incremental algorithm for computing the modular decomposition of 2-structure [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 previous O(n²) 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. |
| File Format | |
| Journal | Algorithmica |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Modular Decomposition Incremental Algorithm Undirected Graph Data Structure Practical Use Relational System Prime Tree Family 2-structures Arises Sophisticated Data Structure Edge-colored Graph Special Case Combinatorial Optimization Problem |
| Content Type | Text |
| Resource Type | Article |
