Local Algorithms in Unit-Disk Graphs

You do not have a Java plugin installed.

Help

New nodes can be added into the graph by clicking points in the plane. Nodes can be removed from the graph by clicking them again. The communication graph is automatically updated and displayed.

The sidebar lists the implemented algorithms along with a set of options for displaying the unit disks and the grid used by the current algorithm. When an algorithm is chosen by selecting the corresponding radio button, the result of the computation is displayed in the graph.

When the result of the algorithm is a set of nodes as in the vertex cover or dominating set, the nodes part of the result set are coloured green. Nodes not part of the resulting set are coloured red.

When the algorithm computes a set of edges instead (as in maximal matching), the edges in the result are drawn as blue double-weight lines.

The mouse wheel can be used to adjust the zoom level.

References

Analysing local algorithms in location-aware quasi unit-disk graphs