Distributed Graph Algorithms

1 Port-numbering model

Definition 1 Port-numbered network
#

A port-numbered network is …TODO: Henrik

Definition 2 PN model
#

TODO: Henrik

Definition 3 LOCAL model
#

TODO: Shreyas

Lemma 4 PN algorithm is a LOCAL algorithm
#

TODO: Shreyas

Definition 5 Covering map
#

TODO: Henrik

Definition 6 Topology view
#

TODO: Shreyas

Definition 7 State view
#

TODO: Shreyas

1.1 Refinement

Definition 8 Refinement of PN
#
Definition 9 Refinement of LOCAL
#

1.1.1 Application

Color reduction:

  • Fast color reduction using Cole-Vishkin to get to \(\Delta ^2\) color.

  • Greedy color reduction from \(\Delta ^2\) to \(\Delta \).

  • Faster color reduction from \(\Delta ^2\) to \(\Delta \).

Compose 1 & 2 or 1 & 3.

1.2 Grand application

We are thinking about it.