The hardness of the grid problemGi Under the Routine Resolution Method

DOI10.1002/MALQ.19870330110MaRDI QIDQ3721813zbMATH OpenOpenAlexFDO

Authors Wenqi Huang, Chusheng Lai, Zhi-Xiang Chen

Publication date 1987

Published in Zeitschrift für Mathematische Logik und Grundlagen der Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19870330110

zbMATH Keywords

clausesconjunctive normal formNP problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Almost polynomial hardness of node-disjoint paths in grids
• Almost polynomial hardness of node-disjoint paths in grids
• On the irregularity strength of them ×n grid
• The hardness of embedding grids and walls
• The complexity of optimization on grids
• On the parameterized complexity of grid contraction
• On the Parameterized Complexity Of Grid Contraction
• A catalog of Hanan grid problems
• NP-completeness for minimizing maximum edge length in grid embeddings
• scientific article; zbMATH DE number 1830732

This page was built for publication: The hardness of the grid problemGi Under the Routine Resolution Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3721813)