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.


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.