графы с помеченными вершинами

Reconstruction of a Labeled Graph by a Graph-walking Mobile Agent

Authors: Sapunov S. V.

The problem of construction of graph-like operational environment by a mobile agent is considered. The model of environment is defined as a simple undirected vertex labeled graph. We propose a polynomial time algorithm of graph reconstruction and labeling for the collective consisting of agent-explorer and agent-supervisor.

On upper bound of vertex distinguishing word length on vertex labeled graph

Authors: Sapunov S. V.

The problem of vertex distinguishing on vertex labeled graphs is considered. Two vertices are called distinguishable if associated languages over the alphabet of labels are different. A linear upper bound of vertex distinguishing word length equal to half the number of vertices is obtained.