Geodesic
Grid minors in damaged grids
David Eppstein1
1University of California, Irvine
The electronic journal of combinatorics, Tome 21 (2014) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
David Eppstein. Grid minors in damaged grids. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/3872

Cité par Sources :