Incremental construction of 2-structures

DOI10.1016/0012-365X(94)90107-4MaRDI QIDQ1322177zbMATH OpenFDO

Authors Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Publication date 15 September 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)90107-4

zbMATH Keywords

directed graphgraphlabeled 2-structurelabelspolynomial algorithmtree

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

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.

Recommendations

• Theory of 2-structures. II: Representation through labeled tree families
• Group based graph transformations and hierarchical representations of graphs
• Dynamic labeled 2-structures
• Partial (set) 2-structures. I: Basic notions and the representation problems
• A characterization of set representable labeled partial 2-structures through decompositions

Cites work

• A Fast Algorithm for the Decomposition of Graphs and Posets
• A Homomorphism Theorem for Finite Graphs
• Graphs indecomposable with respect to the X-join
• scientific article; zbMATH DE number 3668302 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Modules of Coherent Binary Systems
• Partially ordered sets and their comparability graphs
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Theory of 2-structures. II: Representation through labeled tree families
• Transitiv orientierbare Graphen

Cited in

(11)

• A characterization of set representable labeled partial 2-structures through decompositions
• An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
• From modular decomposition trees to rooted median graphs
• scientific article; zbMATH DE number 591000 (Why is no real title available?)
• Dynamic labeled 2-structures
• Theory of 2-structures
• Group based graph transformations and hierarchical representations of graphs
• Efficient Construction of 2-Chains with a Prescribed Boundary
• Dynamic labeled 2-structures with variable domains
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• Theory of 2-structures. II: Representation through labeled tree families

This page was built for publication: Incremental construction of 2-structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1322177)