Average case analysis of Greedy algorithms for Kelly´s triangle problem and the independent set problem

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 problem is the well-known 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-sited and they therefore typically use limited amounts of information. They are thus often suitable for concurrent implementation.