Graph Structure Theory and Applications to Algorithms

图结构理论及其在算法中的应用

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

The central theme of this proposal is graph structure theory and its applications to algorithms. More specifically, the PI will investigate the structure of graphs pertaining to the graph minor inclusion and its much less understood counterpart for directed graphs. Recent work of the PI suggests that it should be possible to obtain much improved bounds in key results of the Graph Minors theory. Such improved bounds will have immediate applications to the design of efficient algorithms. For directed graphs the main questions are whether the so-called cylindrical grid conjecture is true, and whether the algorithms for digraphs of bounded tree-width that are currently known can be improved to become fixed parameter tractable. The cylindrical grid conjecture seems to be both a fundamental mathematical problem as well as one that could potentially unlock many algorithmic applications. The PI also proposes a new approach to attacking Negami's planar cover conjecture, a problem from 1988 that has received a considerable amount of attention. The original motivation came from computer science, the idea being that if a graph G covers a graph H, then the connections of H can be simulated by G, and yet G could potentially have a simpler structure. Negami's conjecture would characterize graphs that have a planar cover.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 underlying 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.

这个提议的中心主题是图结构理论及其在算法中的应用。 更具体地说，PI将研究与图的子包含有关的图的结构，以及它在有向图中较少被理解的对应部分。 PI最近的工作表明，应该可以在图次项理论的关键结果中获得更好的边界。 这种改进的界限将直接应用于设计有效的算法。 对于有向图的主要问题是所谓的圆柱形网格猜想是否正确，以及目前已知的有界树宽有向图的算法是否可以改进为固定参数易处理。 圆柱网格猜想似乎既是一个基本的数学问题，也是一个可能解开许多算法应用的问题。 PI还提出了一种新的方法来攻击Negami的平面覆盖猜想，这个问题从1988年开始就受到了相当多的关注。 最初的动机来自计算机科学，其想法是，如果图G覆盖图H，那么H的连接可以由G模拟，但G可能具有更简单的结构。Negami猜想刻画了具有平面覆盖的图的特征。这项工作福尔斯属于图论领域，与理论计算机科学和数学规划（运筹学）密切相关。图是一个抽象的数学概念，用于对网络进行建模，例如电话网络，交通网络或互联网。在研究这种网络的过程中会出现各种问题，而本建议关注的是结构性问题。 为什么有些网络具有某些特定的理想属性，而另一些则没有？一个令人满意的答案可以有许多应用，从更好地理解底层结构，到设计有效的算法，再到实际计算。 例如，PI早些时候回答的一个这样的问题解决了1913年的格鲁吉亚波利亚问题，它还解决了一个困扰理论计算机科学家四分之一个世纪的不同问题，并在经济学中有应用。

项目成果

Cyclically five-connected cubic graphs

循环五连通立方图

• DOI: 10.1016/j.jctb.2017.03.003
• 发表时间: 2017
• 期刊: Series B
• 作者: Robertson, Neil;Seymour, P.D.;Thomas, Robin
• 通讯作者: Thomas, Robin

Non-embeddable extensions of embedded minors

嵌入式未成年人的不可嵌入式扩展

• DOI: 10.1016/j.jctb.2018.01.004
• 发表时间: 2018
• 期刊: Series B
• 作者: Hegde, Rajneesh;Thomas, Robin
• 通讯作者: Thomas, Robin

A new proof of the flat wall theorem

平壁定理的新证明

• DOI: 10.1016/j.jctb.2017.09.006
• 发表时间: 2018
• 期刊: Series B
• 作者: Kawarabayashi, Ken-ichi;Thomas, Robin;Wollan, Paul
• 通讯作者: Wollan, Paul

K 6 minors in large 6-connected graphs

大 6 连通图中的 K 6 个次要

• DOI: 10.1016/j.jctb.2017.09.007
• 发表时间: 2018
• 期刊: Series B
• 作者: Kawarabayashi, Ken-ichi;Norine, Serguei;Thomas, Robin;Wollan, Paul
• 通讯作者: Wollan, Paul

K 6 minors in 6-connected graphs of bounded tree-width

有界树宽的 6 连通图中的 K 6 个次要

• DOI: 10.1016/j.jctb.2017.08.006
• 发表时间: 2017
• 期刊: Series B
• 作者: Kawarabayashi, Ken-ichi;Norine, Serguei;Thomas, Robin;Wollan, Paul
• 通讯作者: Wollan, Paul