Succinct Encodings of Graph Isomorphism

DOI10.1007/978-3-319-04921-2_23MaRDI QIDQ5404919zbMATH OpenOpenAlexFDO

Authors Bireswar Das, Patrick Scharpfenecker, Jacobo Torán

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) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)

Recommendations

• Succinct encoding of arbitrary graphs
• Succinct Representations of Arbitrary Graphs
• On the succinct representation of graphs
• A note on succinct representations of graphs
• Efficient Suboptimal Graph Isomorphism
• Succinct representations of graphs
• Succinct representations of separable graphs
• Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs
• scientific article; zbMATH DE number 477971
• Approximate graph isomorphism

Cited in

(7)

• Bounded-depth succinct encodings and the structure they imply on graphs
• Succinct encoding of arbitrary graphs
• Succinct encodings for families of interval graphs
• On the structure of solution-graphs for Boolean formulas
• Compressed tree canonization
• Hashing and canonicalizing Notation 3 graphs
• CNF and DNF succinct graph encodings

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

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