Grid Minors in Damaged Grids

被引：0
作者：
Eppstein, David [1 ]
机构：
[1] Univ Calif Irvine, Dept Comp Sci, Irvine, CA 92697 USA
来源：
ELECTRONIC JOURNAL OF COMBINATORICS | 2014年 / 21卷 / 03期
基金：
美国国家科学基金会;
关键词：
GRAPH MINORS; TREE-WIDTH; TREEWIDTH; CODES; PATHWIDTH; THEOREM;
D O I：
暂无
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We prove upper and lower bounds on the size of the largest square grid graph that is a subgraph, minor, or shallow minor of a graph in the form of a larger square grid from which a specified number of vertices have been deleted. Our bounds are tight to within constant factors. We also provide less-tight bounds on analogous problems for higher-dimensional grids.
引用
收藏
页数：19
相关论文
共 30 条
  • [1] Tree-width of graphs without a 3 x 3 grid minor
    Birmele, E.
    Bondy, J. A.
    Reed, B. A.
    [J]. DISCRETE APPLIED MATHEMATICS, 2009, 157 (12) : 2577 - 2596
  • [2] A partial k-arboretum of graphs with bounded treewidth
    Bodlaender, HL
    [J]. THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) : 1 - 45
  • [3] On the Hadwiger's conjecture for graph products
    Chandran, L. Sunil
    Sivadasan, Naveen
    [J]. DISCRETE MATHEMATICS, 2007, 307 (02) : 266 - 273
  • [4] The treewidth and pathwidth of hypercubes
    Chandran, LS
    Kavitha, T
    [J]. DISCRETE MATHEMATICS, 2006, 306 (03) : 359 - 365
  • [5] Approximation algorithms for Euler genus and related problems
    Chekuri, Chandra
    Sidiropoulos, Anastasios
    [J]. 2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, : 167 - 176
  • [6] Chekuri Chandra, 2013, ARXIV13056577
  • [7] Reconfiguring arrays with faults .1. Worst-case faults
    Cole, RJ
    Maggs, BM
    Sitaraman, RK
    [J]. SIAM JOURNAL ON COMPUTING, 1997, 26 (06) : 1581 - 1611
  • [8] Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction
    Demaine, Erik D.
    Hajiaghayi, MohammadTaghi
    Kawarabayashi, Ken-ichi
    [J]. ALGORITHMICA, 2009, 54 (02) : 142 - 180
  • [9] Diestel R, 2004, ABH MATH SEM HAMBURG, V74, P237
  • [10] Highly connected sets and the excluded grid theorem
    Diestel, R
    Jensen, TR
    Gorbunov, KY
    Thomassen, C
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 75 (01) : 61 - 73
123