Geodesic
Grid minors in damaged grids
David Eppstein1
1University of California, Irvine
The electronic journal of combinatorics, Tome 21 (2014) no. 3

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv
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.
DOI : 10.37236/3872
Classification : 05C83, 05C12
Mots-clés : grid graphs, graph minors, subgraphs, shallow minors, treewidth, vertex deletion

David Eppstein  1

1 University of California, Irvine 
David Eppstein. Grid minors in damaged grids. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/3872
@article{10_37236_3872,
     author = {David Eppstein},
     title = {Grid minors in damaged grids},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {3},
     doi = {10.37236/3872},
     zbl = {1300.05292},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3872/}
}
TY  - JOUR
AU  - David Eppstein
TI  - Grid minors in damaged grids
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3872/
DO  - 10.37236/3872
ID  - 10_37236_3872
ER  - 
%0 Journal Article
%A David Eppstein
%T Grid minors in damaged grids
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3872/
%R 10.37236/3872
%F 10_37236_3872

Cité par Sources :