Skip to main content
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Source Link

To give you a particular application where it is useful to think about infinite graphs, consider a network of distributed nodes, each of which runs a distributed algorithm that proceeds in rounds. In every round a node can update its state by performing local computation and communicate by sending/receiving messages to/from its neighbors. The output of such an algorithm is the combined output of all nodes. For example, every node could locally decide whether it is part of an independent set.

Certain distributed computing problems can be solved in constant time (i.e. constant number of rounds until all nodes terminate), no matter how many nodes are in the network. In particular, any such algorithm will work on an infinite (but locally finite) graph. That said, many classic problems (like MIS) are subject to a lower bound of $\Omega(\log^* n)$ and thus cannot be computed on an infinite network.

Further discussion on this point can be found herehere.

To give you a particular application where it is useful to think about infinite graphs, consider a network of distributed nodes, each of which runs a distributed algorithm that proceeds in rounds. In every round a node can update its state by performing local computation and communicate by sending/receiving messages to/from its neighbors. The output of such an algorithm is the combined output of all nodes. For example, every node could locally decide whether it is part of an independent set.

Certain distributed computing problems can be solved in constant time (i.e. constant number of rounds until all nodes terminate), no matter how many nodes are in the network. In particular, any such algorithm will work on an infinite (but locally finite) graph. That said, many classic problems (like MIS) are subject to a lower bound of $\Omega(\log^* n)$ and thus cannot be computed on an infinite network.

Further discussion on this point can be found here.

To give you a particular application where it is useful to think about infinite graphs, consider a network of distributed nodes, each of which runs a distributed algorithm that proceeds in rounds. In every round a node can update its state by performing local computation and communicate by sending/receiving messages to/from its neighbors. The output of such an algorithm is the combined output of all nodes. For example, every node could locally decide whether it is part of an independent set.

Certain distributed computing problems can be solved in constant time (i.e. constant number of rounds until all nodes terminate), no matter how many nodes are in the network. In particular, any such algorithm will work on an infinite (but locally finite) graph. That said, many classic problems (like MIS) are subject to a lower bound of $\Omega(\log^* n)$ and thus cannot be computed on an infinite network.

Further discussion on this point can be found here.

Source Link
Peter
  • 1.3k
  • 7
  • 11

To give you a particular application where it is useful to think about infinite graphs, consider a network of distributed nodes, each of which runs a distributed algorithm that proceeds in rounds. In every round a node can update its state by performing local computation and communicate by sending/receiving messages to/from its neighbors. The output of such an algorithm is the combined output of all nodes. For example, every node could locally decide whether it is part of an independent set.

Certain distributed computing problems can be solved in constant time (i.e. constant number of rounds until all nodes terminate), no matter how many nodes are in the network. In particular, any such algorithm will work on an infinite (but locally finite) graph. That said, many classic problems (like MIS) are subject to a lower bound of $\Omega(\log^* n)$ and thus cannot be computed on an infinite network.

Further discussion on this point can be found here.