Abstract
Greedy algorithms for two elementary graph-theoretic problems are studied for large random problem instances by showing that the behavior of the algorithms is asymptotically deterministic when the problem size tends to infinity. The first problem is the triangle problem posed by F. Kelly and is related to the problem of finding alternate routes in a circuit-switched communication network. The other is the problem of finding large sets of nodes in a graph so that no two of the nodes are neighbors. Greedy algorithms are, by definition, short-sighted and they therefore typically use limited amounts of information. They are thus often suitable for concurrent implementation.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1455-1460 |
| Number of pages | 6 |
| Journal | Proceedings of the IEEE Conference on Decision and Control |
| State | Published - 1987 |
ASJC Scopus subject areas
- Control and Optimization
- Control and Systems Engineering
- Modeling and Simulation