A generalization of the pentomino exclusion problem: dislocation of graphs (Q864131): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4529658 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3903001 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4313096 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Perfect Codes in the Lee Metric and the Packing of Polyominoes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the pentomino exclusion problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algebraic approach to fasciagraphs and rotagraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Linear and combinatorial optimization in ordered algebraic structures / rank | |||
Normal rank |
Latest revision as of 14:06, 25 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A generalization of the pentomino exclusion problem: dislocation of graphs |
scientific article |
Statements
A generalization of the pentomino exclusion problem: dislocation of graphs (English)
0 references
13 February 2007
0 references
A pattern formed by the connection of a specified number of equal-sized squares along common edges is called a polyomino, and if a polyomino is made up of five squares then it is called a pentomino. The concept of polyomino is due to Golomb who also proposed the following pentomino exclusion problem: Find the minimum number, denoted by \(P(k,n)\), of unit squares to be placed on a \((k\times n)\) chessboard so as to exclude all pentominoes. In this paper, this problem is solved for the \((5\times n)\) grid and some upper and lower bounds are provided for the \((k\times n)\) grid for all \(k\) and \(n\). The generalization of the problem to graphs, called the \(\Delta\)-dislocation problem, amounts to finding the minimum number of vertices to be removed from a graph so that all the remaining connected components have cardinality at most \(\Delta\). The algorithmic aspects of the \(\Delta\)-dislocation problem is also discussed, and it is shown that the problem of calculating the value of \(P(k,n)\) has a solution with a running time, with \(k\) fixed, being polynomial in \(n\).
0 references
fasciagraph
0 references