• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

The Square Tiling Problem is NP-Complete for Deterministic Tile Sets

Ville Lukkarila, The Square Tiling Problem is NP-Complete for Deterministic Tile Sets. TUCS Technical Reports 754, Turku Centre for Computer Science, 2006.

Abstract:

It is shown that the square tiling problem of Garey, Johnson
and Papadimitrou is NP-complete even if the given tile set is
deterministic by any two sides, i.e. the colors of any two
sides uniquely determine a tile within the given tile set.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tLukkarila06a,
  title = {The Square Tiling Problem is NP-Complete for Deterministic Tile Sets},
  author = {Lukkarila, Ville},
  number = {754},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2006},
  keywords = {deterministic tiles, NP-completeness, square tiling problem, tiling problem, Wang tiles},
  ISBN = {952-12-1698-0},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication