K-PSEUDOSNAKES IN LARGE GRIDS
AutorMatamala Vasquez, Martin Ignacio
Rapaport Zimermann, Ivan
We study the problem of finding maximum induced subgraphs of bounded maximum degree k-so-called “k-pseudosnakes”- in D-dimensional grids with all side lengths large. We prove several asymptotic upper bounds and give several lower bounds based on constructions. The constructions turn out to be asymptotically optimal for every D when k = 0, 1,D, 2D - 2, 2D - 1 and 2D.
N° de proyecto1010442
ConcursoConcurso Nacional Regular 2001
Título del libro