Logical Approaches to Computational Barriers

DOI10.1007/11780342zbMath1145.68435OpenAlexW4255986326WikidataQ55968647 ScholiaQ55968647MaRDI QIDQ5898822

Johannes Köbler

Publication date: 30 April 2007

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

Full work available at URL: https://doi.org/10.1007/11780342

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Computational complexity of reconstruction and isomorphism testing for designs and line graphs ⋮ The journey of graph kernels through two decades ⋮ Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$ ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ Colored hypergraph isomorphism is fixed parameter tractable ⋮ Graph matching using the interference of continuous-time quantum walks ⋮ On the Complexity of Matroid Isomorphism Problems