Name
Abstract | ||
|---|---|---|
The prime tree decomposition of graphs facilitates the solution of a number of important combinatorial problems. The decomposition is also known as modular decomposition and substitution decomposition . It has been generalized to 2-structures and to k -ary relations, but while both of these generalizations give the decomposition on graphs as a special case, neither is a generalization of the other. In this paper, we propose a type of edge-colored hypergraph, which we will call a k -structure. We define the modular decomposition of k -structures, and generalize the essential algebraic properties. This unifies the prime tree decompositions on 2-structures and k -ary relations, by giving them as special cases, and extends the decomposition to k -structures that are neither 2-structures nor k -ary relations. In addition, we show that any indecomposable k -structure on n ⩾3 nodes contains a smaller indecomposable substructure that has at least n − k nodes. This is a generalization of a previously known result on graphs and 2-structures, that is, where k = 2. The generalization to k -ary relations that it gives as a special case is also new. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0304-3975(94)90233-X | Theor. Comput. Sci. |
Keywords | DocType | Volume |
k-structure generalization | Journal | 132 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 11 |
PageRank | References | Authors |
1.46 | 18 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Ehrenfeucht | 1 | 1823 | 497.83 |
| R. McConnell | 2 | 11 | 1.46 |