Premium
Social network coordination and graph routing
Author(s) -
Onn Shmuel,
Sperber Elisheva
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10057
Subject(s) - computer science , static routing , bipartite graph , routing (electronic design automation) , robot , policy based routing , theoretical computer science , distributed computing , computer network , graph , routing protocol , artificial intelligence
We consider the problem of coordinating robots moving on a network. Each robot is autonomous and needs to visit various sites of the network at various times. The sequence of destinations for each robot changes dynamically and unpredictably. Recently, Onn and Tennenholtz showed that the problem can be solved by introducing a social law on the network, which, once obeyed by all robots, enables each to move to any desired destination without collisions and regardless of the actions of other robots, needing neither central coordination nor mutual communication. This social law can be derived from a suitably defined routing of the graph underlying the network. Here, we study the complexity of routing. We provide an effective characterization of 2‐routable graphs, and by establishing a correspondence between hypergraph coloring and graph routing, we show that computing or approximating an optimal routing is generally hard. We also discuss routing in planar graphs, which often underlie robotic networks and show that the correspondence between coloring and routing together with the Four Color Theorem guarantee the existence of small and effectively computable routings in bipartite planar graphs of small radius. The complexity of routing arbitrary planar graphs remains open. © 2002 Wiley Periodicals, Inc.