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?

$\endgroup$
  • $\begingroup$ The usual rule is one question per post. $\endgroup$ – Yuval Filmus May 22 '17 at 20:40
  • $\begingroup$ Have you tried looking at the papers? They might state the running time. $\endgroup$ – Yuval Filmus May 22 '17 at 20:40
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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