Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction

被引：0
作者：
Erik D. Demaine
MohammadTaghi Hajiaghayi
Ken-ichi Kawarabayashi
机构：
[1] MIT Computer Science and Artificial Intelligence Laboratory,Department of Computer Science
[2] Carnegie Mellon University,undefined
[3] National Institute of Informatics,undefined
来源：
Algorithmica | 2009年 / 54卷
关键词：
Graph minors; Graph algorithms; Grid graphs; Treewidth; Bidimensionality; Wagner’s conjecture;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We explore three important avenues of research in algorithmic graph-minor theory, which all stem from a key min-max relation between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory of Robertson and Seymour, which ultimately proves Wagner’s Conjecture about the structure of minor-closed graph properties.
引用
收藏
页码：142 / 180
页数：38
相关论文
共 88 条
[1]  
Alber J.(2002)Fixed parameter algorithms for dominating set and related problems on planar graphs Algorithmica 33 461-493
[2]  
Bodlaender H.L.(2004)Parameterized complexity: exponential speed-up for planar graph problems J. Algorithms 52 26-56
[3]  
Fernau H.(2002) minors in graphs of bounded tree-width J. Comb. Theory Ser. B 86 133-147
[4]  
Kloks T.(2001)Vertex cover: further observations and further improvements J. Algorithms 41 280-301
[5]  
Niedermeier R.(2001)Approximation algorithms for independent sets in map graphs J. Algorithms 41 20-40
[6]  
Alber J.(2002)Map graphs J. ACM 49 127-138
[7]  
Fernau H.(2007)Quickly deciding minor-closed parameters in general graphs Eur. J. Comb. 28 311-314
[8]  
Niedermeier R.(2004)Bidimensional parameters and local treewidth SIAM J. Discrete Math. 18 501-511
[9]  
Böhme T.(2004)Approximation algorithms for classes of graphs excluding single-crossing graphs as minors J. Comput. Syst. Sci. 69 166-195
[10]  
Maharry J.(2005)Fixed-parameter algorithms for ( ACM Trans. Algorithms 1 33-47
123456789