Incremental construction of 2-structures
type: Item
instance of: scholarly article
title: Incremental construction of 2-structures
zbMATH Open document ID: 0796.05083
DOI: 10.1016/0012-365X(94)90107-4
published in: Discrete Mathematics
publication date: 1994-09-15T00:00:00Z
review text: A labeled 2-structure \(g\) is an edge-labeled directed graph with a reversibility condition on the labels. Each labeled 2-structure \(g\) can be represented as a tree. The trees arising this way are characterized and a polynomial algorithm to recognize them is given.
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 562586
zbMATH Keywords: graph
zbMATH Keywords: labeled 2-structure
zbMATH Keywords: directed graph
zbMATH Keywords: labels
zbMATH Keywords: tree
zbMATH Keywords: polynomial algorithm
author: Andrzej Ehrenfeucht
author: Tero Harju
author: Grzegorz Rozenberg
reviewed by: Martin Loebl
MaRDI profile type: Publication
cites work: Q4091421
cites work: A Homomorphism Theorem for Finite Graphs
cites work: Modules of Coherent Binary Systems
cites work: A Fast Algorithm for the Decomposition of Graphs and Posets
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: Transitiv orientierbare Graphen
cites work: Q3865813
cites work: Partially ordered sets and their comparability graphs
cites work: Graphs indecomposable with respect to the X-join
description: scientific article; zbMATH DE number 562586