5
$\begingroup$

It is still open whether also Luks’ efficient GI algorithm for graphs with bounded degree is parallelizable i.e. NC.

I get this from the survey "On Graph Isomorphism for Restricted Graph Classes" by Johannes Köbler (see this)

My question : Luks has given an algorithm for trivalent GI (degree at most three ) (see section 2). Is that algorithm also not parallelizable ? If yes provide the reference.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.