Identification of vertices of vertex-labeled graphs

MaRDI QIDQ2879974zbMATH OpenFDO

Authors I. S. Grunskij, S. V. Sapunov

Publication date 10 April 2012

Published in Trudy Instituta Prikladnoĭ Matematiki i Mekhaniki (Search for Journal in Brave)

zbMATH Keywords

self-locationtopological environmentvertex-labeled graphs

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Review text

The self-location problem for mobile agents in a topological environment is considered. The environment is modeled by a vertex-labeled graph. An agent can move on the graph's edges and observe the labels of vertices. A finite sets of words over the vertex-label alphabet distinguishing a given vertex from the others, called vertex identifier, is proposed. Existence conditions and complexity estimations for vertex identifiers are obtained and construction methods are developed.

Recommendations

• On mobile agent self-location using topological properties of environment
• Reconstruction of a labeled graph by a graph-walking mobile agent
• Linguistic representation of vertex-labeled graphs
• About a construction method of indistinguishability relations for vertex labeled graphs
• Deterministic rendezvous in graphs

Cited in

(4)

• On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths
• On mobile agent self-location using topological properties of environment
• Reconstruction of a labeled graph by a graph-walking mobile agent
• Vertex labeling of spider graph

This page was built for publication: Identification of vertices of vertex-labeled graphs

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