Buchumschlag

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	MIT Hardness Group, Abel, Zachary, Demaine, Erik D., Diomidova, Jenny, Li, Jeffery, Zhou, Zixiang
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Tetris with Few Piece Types
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
von: MIT Hardness Group, et al.
Veröffentlicht: (2025)

Tetris is Hard with Just One Piece Type
von: MIT Hardness Group, et al.
Veröffentlicht: (2026)

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
von: MIT Gadgets Group, et al.
Veröffentlicht: (2020)

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

Complexity of 2D Snake Cube Puzzles
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
von: Ani, Hayashi, et al.
Veröffentlicht: (2024)

Undecidability of Tiling with a Tromino
von: ULB CompGeom Group, et al.
Veröffentlicht: (2025)

Graph Threading with Turn Costs
von: Demaine, Erik D., et al.
Veröffentlicht: (2024)

Translational Aperiodic Sets of 7 Polyominoes
von: Yang, Chao, et al.
Veröffentlicht: (2024)

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
von: Oka, Keigo, et al.
Veröffentlicht: (2026)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
von: Bai, Tian, et al.
Veröffentlicht: (2026)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
von: Hörsch, Florian, et al.
Veröffentlicht: (2025)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
von: Cai, Jin-Yi, et al.
Veröffentlicht: (2026)

Maximum Reachability Orientation of Mixed Graphs
von: Hörsch, Florian
Veröffentlicht: (2025)

Dynamic Planar Graph Isomorphism is in DynFO
von: Datta, Samir, et al.
Veröffentlicht: (2026)

Undecidability of Translational Tiling with Three Tiles
von: Yang, Chan, et al.
Veröffentlicht: (2024)

Folding One Polyhedral Metric Graph into Another
von: Chung, Lily, et al.
Veröffentlicht: (2024)

Geometry Matters in Planar Storyplans
von: Dobler, Alexander, et al.
Veröffentlicht: (2025)

Tiling with Three Polygons is Undecidable
von: Demaine, Erik D., et al.
Veröffentlicht: (2024)

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
von: Yang, Chao, et al.
Veröffentlicht: (2024)

Recognizing 2-Layer and Outer $k$-Planar Graphs
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2024)

Linear Planar 3-SAT and Its Applications in Planning
von: Desbois, Victorien, et al.
Veröffentlicht: (2025)

The Parameterized Complexity of Geometric 1-Planarity
von: Firbas, Alexander
Veröffentlicht: (2026)

The Parameter Report: An Orientation Guide for Data-Driven Parameterization
von: Komusiewicz, Christian, et al.
Veröffentlicht: (2025)

Self-Assembly of Patterns in the abstract Tile Assembly Model
von: Drake, Phillip, et al.
Veröffentlicht: (2024)

Intrinsic Universality in Seeded Active Tile Self-Assembly
von: Gomez, Tim, et al.
Veröffentlicht: (2024)

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
von: Hamm, Thekla, et al.
Veröffentlicht: (2026)

Hexasort -- The Complexity of Stacking Colors on Graphs
von: Klocker, Linus, et al.
Veröffentlicht: (2026)

Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes
von: Yang, Chao, et al.
Veröffentlicht: (2024)

Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
von: Yang, Chao, et al.
Veröffentlicht: (2024)

Structural Parameters for Steiner Orientation
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2025)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2025)

A Linear Kernel for Planar Vector Domination
von: Sahili, Mahabba El, et al.
Veröffentlicht: (2023)

Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets
von: DeStefano, Zachary, et al.
Veröffentlicht: (2025)

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
von: Fan, Austen, et al.
Veröffentlicht: (2026)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
von: Demaine, Erik D., et al.
Veröffentlicht: (2024)