Graph Structure, Coloring, Flows and Algorithms

图结构、着色、流程和算法

• 批准号: 0701077
• 负责人: Robin Thomas
• 金额: $ 50万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-07-01 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0701077&HistoricalAwards=false
• 关键词: Graph; Structure; Coloring; Flows; Algorithms

The central theme of this proposal is graph structure theory and its applications to coloring, flows and algorithms. More specifically, the principal investigator studies the structure of graphs pertaining to the graph minor inclusion and its relatives, such as the directed minor and matching minor relations, and uses those results to attack flow and coloring problems, as well as the problem of characterizing ``Pfaffian graphs". Pfaffian graphs are of interest because they allow efficient computation of perfect matchings, and their rich theory is related to other areas. This research requires the development of new tools in graph structure theory.In particular, the PI proposes an in-depth study of the notion of ``society", originally introduced by Robertson and Seymour.Applications of the theory range from theoretical (the flow conjectures, the double cycle conjecture) to more algorithmic (coloring graphs on surfaces and graphs belonging to a proper minor-closed family).An important method employed in the proof of the Four-Color Theorem is the technique of ``reducibility". While it is essential for the proof, there is almost no associated theory. The PI attempts to develop such a theory for the Four-Color Theorem, for the 5-Flow Conjecture and for the Cycle Double Cover Conjecture. A successful theory of reducibility (if it exists) will hopefully lead to a computer-free proof of the Four-Color Theorem and to proofs of the 5-Flow and Cycle Double Cover Conjectures.This work falls within the area of graph theory, and is closely related to theoretical computer science and mathematical programming (operations research). A graph is an abstract mathematical notion used to model networks, such as telephone networks, transportation networks or the Internet. Various problems arise in the study of such networks, and this proposal is concerned with problems of structural nature. Why do some networks possess certain specific desirable properties, and others do not? A satisfactory answer can have many applications, ranging from better understanding of the undelying structure, to the design of efficient algorithms, to practical computations. For instance, one such question answered earlier by the PI settles a question of Georgia Polya from 1913, it also solves a different problem that baffled theoretical computer scientists for quarter of a century, and has applications in economics.

该提案的中心主题是图结构理论及其在着色、流和算法中的应用。更具体地说，主要研究者研究了与图的未成年人包含及其亲属有关的图的结构，例如定向未成年人和匹配未成年人关系，并使用这些结果来攻击流和着色问题，以及表征“Pfiran图”的问题。普夫图之所以令人感兴趣，是因为它们允许完美匹配的有效计算，并且它们丰富的理论与其他领域有关。这项研究需要在图结构理论中开发新的工具。特别是，PI提出了对最初由Robertson和Seymour引入的“社会”概念的深入研究。该理论的应用范围从理论到实践，（流动图，双循环猜想），（曲面上的着色图和真次闭族图）四色定理证明中的一个重要方法是“约化”技术。虽然这是必不可少的证明，但几乎没有相关的理论。PI试图为四色定理、5流猜想和循环双覆盖猜想发展这样的理论。一个成功的归约理论（如果存在的话）将有望导致四色定理的无计算机证明和5-流和循环双覆盖猜想的证明。这项工作福尔斯图论领域，与理论计算机科学和数学规划（运筹学）密切相关。图是一个抽象的数学概念，用于对网络进行建模，例如电话网络，交通网络或互联网。在研究这种网络的过程中会出现各种问题，而本建议关注的是结构性问题。为什么有些网络具有某些特定的理想属性，而另一些则没有？一个令人满意的答案可以有许多应用，从更好地理解undelying结构，到设计有效的算法，再到实际计算。例如，PI早些时候回答的一个这样的问题解决了1913年的格鲁吉亚波利亚问题，它还解决了一个困扰理论计算机科学家四分之一个世纪的不同问题，并在经济学中有应用。