Mathematical Sciences: RUI: Graph Theory and the Complexity of Graph Algorithms

点击翻译按钮获取中文摘要

This is an award made under the RUI program. Professor Schmeichel will study the structure of graphs in terms of the length of the cycles the graph contains and to examine the algorithmic complexity of various coloring and communication problems on graphs. Graph Theory goes back perhaps two hundred years, but only in the last half-century has the field become an active, fertile, and flourishing branch of mathematics. A graph is a network of lines ("edges") joining points ("vertices"), thus the language of graphs becomes a natural way of describing interrelationships among separated objects. Graph Theory figures most prominently as an essential tool in Communications Theory and Computer Science.