A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus

Publisher Website
Google Scholar
Abstract
The isomorphism problem for graphs has been in recent years the object of a much research (see e.g. [Col 78] or [Re-Cor 77]). Its complexity is still unknown. It is not known whether the problem is NP-complete, although it is NP, of course. It is not known whether there exists a polynomial-time algorithm for it. Recently, Babai [Ba 79] has discussed probabilistic algorithms. For additional information see also [Mi 77]. The problem has also some practical applications. Of the known algorithms let us only quote the work of Weinberg [We 66] and of Hopcroft and Tarjan [Ho-Ta 72]. Weinberg's algorithm rums in quadratic time (in &agr;o, the number of vertices of the graphs). Hopcroft and Tarjan's runs in time 0(&agr;o log&agr;o) and uses their powerful technique of depth-first search. Both these algorithms apply only to planar (Weinberg's only to 3-connected planar) graphs. They rely on a well-known rigidity theorem of Withney [Withney 32].

This publication has 0 references indexed in Scilit: