Detecting almost symmetries of graphs

DOI10.1007/s12532-017-0124-3zbMath1400.05160OpenAlexW2750928229MaRDI QIDQ1621684

Sebastian Pokutta, Ben Knueven, Jim Ostrowski

Publication date: 9 November 2018

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-017-0124-3

zbMATH Keywords

branch-and-boundgraph automorphismalmost symmetries

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

FindAlmostSymmetry

Uses Software

• nauty
• GraphBase
• Traces
• PEBBL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orbital branching
• PEBBL: an object-oriented framework for scalable parallel branch and bound
• A note on the graph isomorphism counting problem
• Zero knowledge and the chromatic number
• Pruning by isomorphism in branch-and-cut
• Exploiting orbits in symmetric ILP
• Practical graph isomorphism. II.
• Approximate Graph Isomorphism
• Algorithms for the Assignment and Transportation Problems
• Relations between average case complexity and approximation complexity
• The graph isomorphism disease
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Graph Drawing
• Graph isomorphism in quasipolynomial time [extended abstract]
• Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
• Asymmetric graphs

This page was built for publication: Detecting almost symmetries of graphs