Computational graph theory has emerged as a powerful medium for the development of algorithmic techniques (e.g., for dynamic algorithms, on-line algorithms, parallel algorithms, approximation algorithms, data structure design, etc.). Graph theory provides an excellent way to model problems related to transportation, network design, optimization, VLSI and many other fields. This allows one to both develop and illustrate the power of different algorithmic tools. This project studies two aspects of efficient algorithm design. The first aspect is the study of intractable problems (many optimization problems fall under this category), and the design of efficient algorithms to obtain approximate solutions. The second aspect is the study of problems that are known to be solvable exactly in polynomial time, but there is a wide gap between the known upper and lower bounds. The specific problems studied are problems that are becoming important in the design of efficient and reliable communication networks. They address issues that are relevant for higher reliability of communication at low cost, and are of interest in network design and in the implementation of broadcast protocols. Some of the tools and ideas that are used in the solutions for these problems will have applications to solving other problems as well.
