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

数学科学：RUI：图论和图算法的复杂性

• 批准号: 9206991
• 负责人: Edward Schmeichel
• 金额: $ 5.64万
• 依托单位: San Jose State University Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-06-15 至 1995-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9206991&HistoricalAwards=false
• 关键词: Mathematical; Sciences; RUI; Graph; Theory

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.

这是RUI计划下的一个奖项。 教授 Schmeichel将研究图的结构， 图中包含的周期的长度，并检查 各种着色和通信的算法复杂度 图上的问题。 图论可以追溯到200年前，但只有 在过去的半个世纪里，这个领域已经成为一个活跃的，肥沃的， 数学的一个繁荣的分支。 图是一个网络， 线（“边缘”）连接点（“顶点”），因此语言的 图表成为描述相互关系的自然方式 分离的物体之间。 图论是最重要的 作为通信理论和计算机的重要工具， 科学