Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
From MaRDI portal
Publication:3590975
DOI10.1007/978-3-540-70918-3_58zbMath1186.68215OpenAlexW1656942156MaRDI QIDQ3590975
Publication date: 3 September 2007
Published in: STACS 2007 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-70918-3_58
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)
Related Items
The isomorphism problem for planar 3-connected graphs is in unambiguous logspace ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems