文章基本信息

标题：Excluded Grid Theorem: Improved and Simplified (Invited Talk)
本地全文：下载
作者：Julia Chuzhoy
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：53
页码：31:1-31:1
DOI：10.4230/LIPIcs.SWAT.2016.31
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：One of the key results in Robertson and Seymour's seminal work on graph minors is the Excluded Grid Theorem. The theorem states that there is a function f, such that for every positive integer g, every graph whose treewidth is at least f(g) contains the (gxg)-grid as a minor. This theorem has found many applications in graph theory and algorithms. An important open question is establishing tight bounds on f(g) for which the theorem holds. Robertson and Seymour showed that f(g)>= \Omega(g^2 log g), and this remains the best current lower bound on f(g). Until recently, the best upper bound was super-exponential in g. In this talk, we will give an overview of a recent sequence of results, that has lead to the best current upper bound of f(g)=O(g^{19}polylog(g)). We will also survey some connections to algorithms for graph routing problems.
关键词：Graph Minor Theory; Excluded Grid Theorem; Graph Routing