Hard tiling problems with simple tiles

DOI10.1007/s00454-001-0047-6zbMath1021.68097DBLPjournals/dcg/MooreR01arXivmath/0003039OpenAlexW2007385106WikidataQ60162832 ScholiaQ60162832MaRDI QIDQ5955147

Moore, Cristopher, John Michael Robson

Publication date: 7 February 2002

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0003039

zbMATH Keywords

tilingshalting problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (61)

Small polyomino packing ⋮ Irregular polyomino tiling via integer programming with application in phased array antenna design ⋮ Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues ⋮ Eulerian disjoint paths problem in grid graphs is NP-complete ⋮ Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity ⋮ On the algorithmic complexity of zero-sum edge-coloring ⋮ Positive planar satisfiability problems under 3-connectivity constraints ⋮ Fast domino tileability ⋮ Maximizing Nash product social welfare in allocating indivisible goods ⋮ The complexity of finding optimal subgraphs to represent spatial correlation ⋮ Approximation of the Quadratic Knapsack Problem ⋮ NP‐completeness of list coloring and precoloring extension on the edges of planar graphs ⋮ Strong partial clones and the time complexity of SAT problems ⋮ The complexity of restricted star colouring ⋮ The complexity of finding common partitions of genomes with predefined block sizes ⋮ An injective version of the 1-2-3 conjecture ⋮ On the semi-proper orientations of graphs ⋮ Planar Embeddings with Small and Uniform Faces ⋮ Complexity of tiling a polygon with trominoes or bars ⋮ \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\) ⋮ Algorithmic complexity of proper labeling problems ⋮ The complexity of generalized domino tilings ⋮ Connecting guards with minimum Steiner points inside simple polygons ⋮ Decomposing subcubic graphs into claws, paths or triangles ⋮ The complexity of binary matrix completion under diameter constraints ⋮ Two-machine interval shop scheduling with time lags ⋮ Tile invariants: New horizons. ⋮ Hardness Results for the Synthesis of b-bounded Petri Nets ⋮ A notion of vertex equitability for proper labellings ⋮ Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ On the Number of Neighbors in Normal Tiling ⋮ Unnamed Item ⋮ Complexity and algorithms for recognizing polar and monopolar graphs ⋮ On minimizing the maximum color for the 1-2-3 conjecture ⋮ On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem ⋮ Reducing the domination number of graphs via edge contractions and vertex deletions ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ Hard coloring problems in low degree planar bipartite graphs ⋮ The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs ⋮ Blocking total dominating sets via edge contractions ⋮ On the \(d\)-claw vertex deletion problem ⋮ Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications ⋮ A covering problem that is easy for trees but \(\mathbf{NP}\)-complete for trivalent graphs ⋮ Minimum entropy orientations ⋮ Rectangular tileability and complementary tileability are undecidable ⋮ Obtaining a proportional allocation by deleting items ⋮ Hard and easy instances of L-tromino tilings ⋮ Decomposing Cubic Graphs into Connected Subgraphs of Size Three ⋮ The complexity of synthesizing elementary net systems relative to natural parameters ⋮ The complexity of the \(L(p,q)\)-labeling problem for bipartite planar graphs of small degree ⋮ Complexity and algorithms for neighbor-sum-2-distinguishing \(\{1,3\}\)-edge-weighting of graphs ⋮ Graph coloring with cardinality constraints on the neighborhoods ⋮ Variations of the maximum leaf spanning tree problem for bipartite graphs ⋮ Edge weights and vertex colours: minimizing sum count ⋮ On the hardness of determining the irregularity strength of graphs ⋮ Using edge contractions to reduce the semitotal domination number ⋮ A new mathematical model for tiling finite regions of the plane with polyominoes ⋮ Ribbon tile invariants from the signed area ⋮ A short scientific biography of Maurice Nivat ⋮ The Complexity of Synthesis of b-Bounded Petri Nets

This page was built for publication: Hard tiling problems with simple tiles