A \(k\)-structure generalization of the theory of 2-structures
type: Item
instance of: scholarly article
title: A \(k\)-structure generalization of the theory of 2-structures
zbMATH Open document ID: 0808.05089
DOI: 10.1016/0304-3975(94)90233-X
author: R. M. McConnell
author: Andrzej Ehrenfeucht
published in: Theoretical Computer Science
publication date: 1994-09-25T00:00:00Z
review text: As the title of this paper indicates the authors deal with \(k\)- structures---a certain generalization of the concept of a 2-structure. After having given the exact definition of a \(k\)-structure, \(k \geq 2\), and a lot of additional definitions, properties and examples dealing with \(k\)-structures, A. Ehrenfeucht and R. McConnell succeeded in proving the main result which says that a primitive \(k\)-structure may be expressed in terms of a chain of ever decreasing primitive substructures. It is remarkable that the very long proof is well readable because the authors pointed out the relationship and the differences between the new theory and the known results concerning the decomposition theory of 2- structures.
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 643674
zbMATH Keywords: \(k\)-structures
zbMATH Keywords: 2-structure
reviewed by: Rainer Bodendiek
MaRDI profile type: Publication
cites work: Graphs with unique maximal clumpings
cites work: Q3852212
cites work: Primitive 2-structures with the \((n-2)\)-property
cites work: Partitive hypergraphs
cites work: Q4281647
cites work: A Combinatorial Decomposition Theory
cites work: An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
cites work: Invariants of inversive 2-structures on groups of labels
cites work: Theory of 2-structures. I: Clans, basic subclasses, and morphisms
cites work: Theory of 2-structures. II: Representation through labeled tree families
cites work: Primitivity is hereditary for 2-structures
cites work: Transitiv orientierbare Graphen
cites work: Q3328583
cites work: On the X-join decomposition for undirected graphs
cites work: Q3128916
cites work: Q3686754
cites work: Almost all comparability graphs are UPO
cites work: Q3683903
cites work: Incremental modular decomposition
cites work: Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
cites work: Partially ordered sets and their comparability graphs
cites work: Optimal Sequencing by Modular Decomposition: Polynomial Algorithms
cites work: \(P_ 4\)-trees and substitution decomposition
cites work: On Comparability and Permutation Graphs
cites work: Q3670598
cites work: Q3042406
cites work: Q3042407
cites work: The Recognition of Series Parallel Digraphs
full work available at URL: 0304-3975(94)90233-x
OpenAlex ID: W2072152386
description: scientific article; zbMATH DE number 643674