# Noon lecture

On 26.6.2009 at 13:00 in S6, there is the following noon lecture:

# On Minimum Metric Dimension of Architectures

## Abstract

A collision-free path for a movable object among obstacles is an interesting problem in the field of robotics. A robot is a mechanical device which is made to move in space with obstructions around. It has neither the concept of direction nor that of visibility. But it is assumed that it can sense the distances to a set of landmarks. Evidently, if the robot knows its distances to a sufficiently large set of landmarks, its position in space is uniquely determined.

Let \$M=\{v_{1},\$ \$v_{2}\$ \$...\$ \$v_{n}\}\$ be an ordered set of vertices in a graph \$G\$. Then \$(d(u,v_{1}),\$ \$d(u,v_{2})\$ \$...\$ \$d(u,v_{n}))\$ is called the \$M\$-coordinates of a vertex \$u\$ of \$G\$. The set \$M\$ is called a metric basis if the vertices of \$G\$ have distinct \$M\$-coordinates. A minimum metric basis is a metric basis \$M\$ with minimum cardinality. If \$M\$ is a metric basis then it is clear that for each pair of vertices \$u\$ and \$v\$ of \$%

Webmaster: kamweb.mff.cuni.cz         Archive page