Imagen de Portada

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	MIT Hardness Group, Abel, Zachary, Demaine, Erik D., Diomidova, Jenny, Li, Jeffery, Zhou, Zixiang
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Tetris with Few Piece Types
por: MIT Hardness Group, et al.
Publicado: (2024)

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

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

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

Tetris is Hard with Just One Piece Type
por: MIT Hardness Group, et al.
Publicado: (2026)

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

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
por: MIT Hardness Group, et al.
Publicado: (2024)

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
por: MIT Hardness Group, et al.
Publicado: (2024)

Complexity of 2D Snake Cube Puzzles
por: MIT Hardness Group, et al.
Publicado: (2024)

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

Undecidability of Tiling with a Tromino
por: ULB CompGeom Group, et al.
Publicado: (2025)

Graph Threading with Turn Costs
por: Demaine, Erik D., et al.
Publicado: (2024)

Translational Aperiodic Sets of 7 Polyominoes
por: Yang, Chao, et al.
Publicado: (2024)

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
por: Oka, Keigo, et al.
Publicado: (2026)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
por: Bai, Tian, et al.
Publicado: (2026)

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

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
por: Cai, Jin-Yi, et al.
Publicado: (2026)

Maximum Reachability Orientation of Mixed Graphs
por: Hörsch, Florian
Publicado: (2025)

Dynamic Planar Graph Isomorphism is in DynFO
por: Datta, Samir, et al.
Publicado: (2026)

Undecidability of Translational Tiling with Three Tiles
por: Yang, Chan, et al.
Publicado: (2024)

Folding One Polyhedral Metric Graph into Another
por: Chung, Lily, et al.
Publicado: (2024)

Geometry Matters in Planar Storyplans
por: Dobler, Alexander, et al.
Publicado: (2025)

Tiling with Three Polygons is Undecidable
por: Demaine, Erik D., et al.
Publicado: (2024)

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

Recognizing 2-Layer and Outer $k$-Planar Graphs
por: Kobayashi, Yasuaki, et al.
Publicado: (2024)

Linear Planar 3-SAT and Its Applications in Planning
por: Desbois, Victorien, et al.
Publicado: (2025)

The Parameterized Complexity of Geometric 1-Planarity
por: Firbas, Alexander
Publicado: (2026)

The Parameter Report: An Orientation Guide for Data-Driven Parameterization
por: Komusiewicz, Christian, et al.
Publicado: (2025)

Self-Assembly of Patterns in the abstract Tile Assembly Model
por: Drake, Phillip, et al.
Publicado: (2024)

Intrinsic Universality in Seeded Active Tile Self-Assembly
por: Gomez, Tim, et al.
Publicado: (2024)

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
por: Hamm, Thekla, et al.
Publicado: (2026)

Hexasort -- The Complexity of Stacking Colors on Graphs
por: Klocker, Linus, et al.
Publicado: (2026)

Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes
por: Yang, Chao, et al.
Publicado: (2024)

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

Structural Parameters for Steiner Orientation
por: Hanaka, Tesshu, et al.
Publicado: (2025)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
por: Eagling-Vose, Tala, et al.
Publicado: (2025)

A Linear Kernel for Planar Vector Domination
por: Sahili, Mahabba El, et al.
Publicado: (2023)

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

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

Continuous Flattening and Reversing of Convex Polyhedral Linkages
por: Demaine, Erik D., et al.
Publicado: (2024)