2
$\begingroup$

From Wolfram:

A polynomial time algorithm is however known for planar graphs (Hopcroft and Tarjan 1973, Hopcroft and Wong 1974) and when the maximum vertex degree is bounded by a constant (Luks 1982; Skiena 1990, p. 181).

What are the running times of such algorithms, in terms of size of the graphs? What algorithms are used in practice for graph isomorphism?

Improve this question
$\endgroup$
2
  • $\begingroup$ The usual rule is one question per post. $\endgroup$
    – Yuval Filmus
    Commented May 22, 2017 at 20:40
  • $\begingroup$ Have you tried looking at the papers? They might state the running time. $\endgroup$
    – Yuval Filmus
    Commented May 22, 2017 at 20:40

1 Answer 1

Reset to default
2
$\begingroup$

Algorithms used in practice differ a lot from theoretical algorithms. One popular software package is nauty. The link should also explain the algorithms used, which probably rely on combinatorial methods.

As for the running times for specific algorithms, they are likely stated in the papers. I suggest checking the references.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.