Decentralized Graph Coloring

• Each node is to choose its own color

• Iterative algorithms:

  • begin with a random coloring
  • iteratively improve
    • each node chooses a color that minimizes its conflicts with its neighbors

• Need to coordinate choice of colors

  • if two neighbors simultaneously choose colors, they may choose the same color
  • i.e., they may introduce a conflict

• Number of colors fixed in advance

  • e.g., by considering latency constraints
    • scan range, speed of target, measurement duration