SGER: A Proposal For Research Into The Jacobians Of Graphs

SGER：研究图的雅可比行列式的提案

• 批准号: 0902717
• 负责人: Richard Lipton
• 金额: $ 20万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-01-15 至 2011-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0902717&HistoricalAwards=false
• 关键词: SGER; Proposal; Research; Into; Jacobians

The design of efficient graph algorithms continues to be one of the central problems of computer science. Graphs can be used to model everything from social networks to biological systems to boolean circuits. There are currently many approaches to the design of graph algorithms, but there still remain many open problems. The proposed research studies a new algebraic approach to the design of efficient graph algorithms that is based on the Jacobian of a graph. Every graph has an abelian group?the Jacobian? that is associated with it. This group is the same for isomorphic graphs, although it does not uniquely determine the graph. However, the Jacobian does contain a great deal of important information about the graph. The plan is to exploit the Jacobian to design new efficient algorithms for important graph problems. Some of the problems that will be studied include: sampling random sub-graphs with specific properties, graph isomorphism for new classes of graphs, and many other problems. The success of the proposed research will significantly increase our understanding of graph algorithms. It will not only discover new algorithms, but will open the door on an entirely new approach to the creation of additional algorithms.

设计有效的图算法仍然是计算机科学的中心问题之一。图形可以用来模拟从社交网络到生物系统再到布尔电路的一切事物。目前，有许多方法来设计图算法，但仍然存在许多悬而未决的问题。该研究提出了一种新的代数方法来设计有效的图算法，这是基于图的雅可比矩阵。每个图都有一个阿贝尔群？雅可比矩阵这个群对于同构图来说是相同的，尽管它并不唯一地确定该图。然而，雅可比矩阵确实包含了大量关于图的重要信息。 该计划是利用雅可比矩阵设计新的有效算法，重要的图形问题。将研究的一些问题包括：具有特定性质的随机子图的采样，新类图的图同构以及许多其他问题。所提出的研究的成功将显着增加我们对图算法的理解。它不仅会发现新的算法，而且会为创建其他算法的全新方法打开大门。