Detecting almost symmetries of graphs

DOI10.1007/S12532-017-0124-3MaRDI QIDQ1621684zbMATH OpenOpenAlexFDO

Authors Ben Knueven, Jim Ostrowski, Sebastian Pokutta

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

almost symmetriesbranch-and-boundgraph automorphism

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2084276
• Detecting symmetries by branch and cut.
• Graph Drawing
• scientific article; zbMATH DE number 2080115
• scientific article; zbMATH DE number 3985261

Cites work

• A note on the graph isomorphism counting problem
• Algorithms for the Assignment and Transportation Problems
• Approximate graph isomorphism
• Asymmetric graphs
• Exploiting orbits in symmetric ILP
• Graph Drawing
• Graph isomorphism in quasipolynomial time (extended abstract)
• Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
• scientific article; zbMATH DE number 437527 (Why is no real title available?)
• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• scientific article; zbMATH DE number 1555923 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Orbital branching
• PEBBL: an object-oriented framework for scalable parallel branch and bound
• Practical graph isomorphism. II.
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Pruning by isomorphism in branch-and-cut
• Relations between average case complexity and approximation complexity
• The graph isomorphism disease
• Zero knowledge and the chromatic number

Cited in

(8)

• Detecting symmetries by branch and cut.
• Methods of destroying the symmetries of a graph
• scientific article; zbMATH DE number 2084276 (Why is no real title available?)
• Automatic Symmetry Detection in Well-Formed Nets
• FindAlmostSymmetry
• Coarse distinguishability of graphs with symmetric growth
• Graph Drawing
• Detection of the permutation symmetry in pattern sets

Describes a project that uses

Uses Software

• nauty
• GraphBase
• Traces
• PEBBL

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

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