AVERAGE CASE ANALYSIS OF GREEDY ALGORITHMS FOR KELLEY'S TRIANGLE PROBLEM AND THE INDEPENDENT SET PROBLEMS.

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)1455-1460
Number of pages6
JournalProceedings of the IEEE Conference on Decision and Control
StatePublished - 1987

ASJC Scopus subject areas

  • Chemical Health and Safety
  • Control and Systems Engineering
  • Safety, Risk, Reliability and Quality

Fingerprint Dive into the research topics of 'AVERAGE CASE ANALYSIS OF GREEDY ALGORITHMS FOR KELLEY'S TRIANGLE PROBLEM AND THE INDEPENDENT SET PROBLEMS.'. Together they form a unique fingerprint.

Cite this