INCREMENTAL CONSTRUCTION OF 2-STRUCTURES

: EHRENFEUCHT A, HARJU T, ROZENBERG G

Publisher: ELSEVIER SCIENCE BV

: 1994

Discrete Mathematics

: DISCRETE MATHEMATICS

: DISCRETE MATH

: 128

: 1-3

: 113

: 141

: 29

: 0012-365X

DOI: https://doi.org/10.1016/0012-365X(94)90107-4

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 prime tree of g. We characterize a labeled 2-structure h in terms of the prime tree of a labeled 2-structure g which results from h by removing one element from h. This leads to an O(n3) algorithm for the construction of the prime tree.

Mathematics