COMMANDITES

Min-max theorems are basic results in graph theory, and are useful in designing polynomial time algorithms for graph problems. However, many graph problems are NP-hard, and thus min-max theorems and polynomial time algorithms do not exist under some well-known complexity assumptions. Recent research has focused on designing polynomial time approximation algorithms for these NP-hard graph problems. In this talk, we will present some graph theoretical approximate min-max theorems, which can be used to obtain polynomial time approximation algorithms for NP-hard graph problems. Also, we will show the applications of these results to a data transmission problem in computer networks.