Local problems, planar local problems and linear time

DOI10.1007/3-540-45793-3_27MaRDI QIDQ4411837zbMATH OpenFDO

Authors Régis Barbanchon, Etienne Grandjean

Publication date 10 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2471/24710397.htm

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Complexity of Planar Counting Problems
• How easy is local search?
• scientific article; zbMATH DE number 515738
• scientific article; zbMATH DE number 152108
• Planar 3DM is NP-complete

Cited in

(5)

• A logical approach to locality in pictures languages
• A Local Criterion for Polynomial-Time Stratified Computations
• On unique graph 3-colorability and parsimonious reductions in the plane
• Graph properties checkable in linear time in the number of vertices
• Hardness of pre-assignment problem for unique minimum vertex cover on planar graphs with maximum degree 3

This page was built for publication: Local problems, planar local problems and linear time

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