A generalization of the pentomino exclusion problem: Dislocation of graphs
| Autor: | Sylvain Gravier, Julien Moncel, Charles Payan |
|---|---|
| Přispěvatelé: | Institut Fourier (IF ), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF), Moncel, Julien, Institut Fourier (IF), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), ROSP (G-SCOP_ROSP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2007 |
| Předmět: |
Discrete mathematics
Connected component dislocation Sublinear function 0102 computer and information sciences pentomino exclusion problem [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Grid 01 natural sciences Upper and lower bounds Graph Theoretical Computer Science 010101 applied mathematics Combinatorics [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] 010201 computation theory & mathematics Algorithmics Golomb coding Pentomino Fasciagraph Discrete Mathematics and Combinatorics 0101 mathematics ComputingMilieux_MISCELLANEOUS MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete Mathematics Discrete Mathematics, Elsevier, 2007, 307 (3-5), pp.435-444 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2005.09.036 |
| Popis: | In this paper, we first investigate the pentomino exclusion problem, due to Golomb. We solve this problem on the 5×n grid and we give some lower and upper bounds for the k×n grid for all k and n.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×n grid graphs, provided k is not part of the input. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect