Breaking symmetry in complete graphs by orienting edges: asymptotic bounds

DOI10.1016/S0020-0190(98)00124-0MaRDI QIDQ293364zbMATH OpenOpenAlexFDO

Authors Frank Harary, Desh Ranjan

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098001240?np=y

zbMATH Keywords

computational complexitygraph algorithmsasymptotic boundidentity orientation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35)

Recommendations

• Destroying symmetry by orienting edges: Complete graphs and complete bigraphs
• scientific article; zbMATH DE number 2124072
• Asymmetric graphs
• Invariant systems of representatives, or the cost of symmetry
• scientific article; zbMATH DE number 1222148

Cites work

• scientific article; zbMATH DE number 1055145 (Why is no real title available?)
• Destroying symmetry by orienting edges: Complete graphs and complete bigraphs
• Parallel concepts in graph theory

Cited in

(4)

• Invariant systems of representatives, or the cost of symmetry
• Destroying symmetry by orienting edges: Complete graphs and complete bigraphs
• Invariance, quasi-invariance, and unimodularity for random graphs
• Optimal symmetry breaking for graph problems

This page was built for publication: Breaking symmetry in complete graphs by orienting edges: asymptotic bounds

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