Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649070 | Discrete Mathematics | 2007 | 10 Pages |
Abstract
In this paper, we first investigate the pentomino exclusion problem, due to Golomb. We solve this problem on the 5×n5×n grid and we give some lower and upper bounds for the k×nk×n grid for all kk and nn.We then give a generalization of this problem in graphs, the ΔΔ-dislocation problem , which consists in finding the minimum number of vertices to be removed from a graph so as all the remaining connected components have cardinality at most ΔΔ.We investigate the algorithmic aspects of the ΔΔ-dislocation problem: we first prove the problem is NP-Complete, then we give a sublinear algorithm which solves the problem on a restricted class of graphs which includes the k×nk×n grid graphs, provided kk is not part of the input.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Sylvain Gravier, Julien Moncel, Charles Payan,