Displaying similar documents to “Graphs associated with codes of covering radius 1 and minimum distance 2.”

Implementation of directed acyclic word graph

Miroslav Balík (2002)

Kybernetika

Similarity:

An effective implementation of a Directed Acyclic Word Graph (DAWG) automaton is shown. A DAWG for a text T is a minimal automaton that accepts all substrings of a text T , so it represents a complete index of the text. While all usual implementations of DAWG needed about 30 times larger storage space than was the size of the text, here we show an implementation that decreases this requirement down to four times the size of the text. The method uses a compression of DAWG elements, i....

Defect theorem in the plane

Włodzimierz Moczurad (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider the defect theorem in the context of labelled polyominoes, , two-dimensional figures. The classical version of this property states that if a set of words is not a code then the words can be expressed as a product of at most words, the smaller set being a code. We survey several two-dimensional extensions exhibiting the boundaries where the theorem fails. In particular, we establish the defect property in the case of three dominoes ( × 1 or 1 × rectangles).

A Note on the Total Detection Numbers of Cycles

Henry E. Escuadro, Futaba Fujie, Chad E. Musick (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a connected graph of size at least 2 and c :E(G)→{0, 1, . . . , k− 1} an edge coloring (or labeling) of G using k labels, where adjacent edges may be assigned the same label. For each vertex v of G, the color code of v with respect to c is the k-vector code(v) = (a0, a1, . . . , ak−1), where ai is the number of edges incident with v that are labeled i for 0 ≤ i ≤ k − 1. The labeling c is called a detectable labeling if distinct vertices in G have distinct color codes. The value...