K-PSEUDOSNAKES IN LARGE GRIDS
AuthorMatamala 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.
ContestConcurso Nacional Regular 2001