Mathematical Sciences: Graph Theory and The Complexity of Graph Algorithms

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

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

This award supports the research in Graph Theory of Professor Edward Schmeichel of San Jose State University. Dr. Schmeichel will investigate the structure of graphs by examining the length of the longest cycle that a graph may contain, and by studying the algorithmic complexity of various problems on graphs and networks. The beginnings of Graph Theory go back perhaps two hundred years, but it is mostly in the last half-century that the field has become an active, fertile, and flourishing branch of mathematics. A graph is a network of lines ("edges") joining points ("vertices"), and the uses of Graph Theory abound not only in the field of Communications Theory but in surprisingly many parts of Mathematics, both pure and applied, as well as Theoretical Computer Science.

该奖项支持圣何塞州立大学Edward Schmeichel教授的图论研究。 Schmeichel 博士将通过检查图可能包含的最长循环的长度以及研究图和网络上各种问题的算法复杂性来研究图的结构。 图论的起源大约可以追溯到两百年前，但主要是在过去的半个世纪里，该领域才成为一个活跃、丰富且蓬勃发展的数学分支。图是由连接点（“顶点”）的线（“边”）组成的网络，图论的用途不仅在通信理论领域，而且在数学（纯数学和应用数学）以及理论计算机科学的许多领域中都有大量应用。