Succinct Encodings of Graph Isomorphism

DOI10.1007/978-3-319-04921-2_23zbMath1362.68228OpenAlexW1020474857MaRDI QIDQ5404919

Patrick Scharpfenecker, Bireswar Das, Jacobo Toran

Publication date: 31 March 2014

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-04921-2_23

zbMATH Keywords

complexitygraph isomorphismCNFDNFsuccinct encoding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)

Related Items (2)

Compressed Tree Canonization ⋮ On the Structure of Solution-Graphs for Boolean Formulas

This page was built for publication: Succinct Encodings of Graph Isomorphism