scientific article; zbMATH DE number 1004939

MaRDI QIDQ4335302zbMATH OpenFDO

Authors Takunari Miyazaki

Publication date 5 January 1998

zbMATH Keywords

automorphismsbacktrackcomputational complexitygadgetsgraph isomorphismhashingMcKay's algorithmpartitionstable vertex colouringsvertex labellings

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• McKay's canonical graph labeling algorithm
• Efficient isomorphism of Miyazaki graphs
• Practical graph isomorphism. II.
• Tight lower and upper bounds for the complexity of canonical colour refinement
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement

Cited in

(15)

• Graph matching using the interference of continuous-time quantum walks
• The computational complexity of cordial and equitable labelling
• Gathering robots in graphs: the central role of synchronicity
• Novel techniques to speed up the computation of the automorphism group of a graph
• New invariants for the graph isomorphism problem
• Information theoretic measures of UHG graphs with low computational complexity
• Tight lower and upper bounds for the complexity of canonical colour refinement
• Practical graph isomorphism. II.
• Symmetry breaking constraints for the minimum deficiency problem
• Efficient isomorphism of Miyazaki graphs
• McKay's canonical graph labeling algorithm
• Benchmark Graphs for Practical Graph Isomorphism
• Dörfler marking with minimal cardinality is a linear complexity problem
• Algorithms for the graph isomorphism problem based on graph deregularisation
• An exponential lower bound for individualization-refinement algorithms for graph isomorphism

Describes a project that uses

Uses Software

• nauty

This page was built for publication:

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