DVP Talk: Takunari Miyazakie, October 1 @ 4 pm in Olin 372


Title: Computing canonical forms of graphs

Abstract: Determining the computational complexity of the problem of finding canonical representatives of graphs is a long-standing unresolved question.  This question is of fundamental interest in the theory of computing because of its close relationship with graph-isomorphism testing.

While the problem may be difficult in general, group-theoretic methods have enabled polynomial-time solutions for important classes of graphs, including graphs of bounded valence.  In practice, however, variants of backtrack search to find lexicographic leaders have long been accepted as quite effective; for example, the system nauty is the leader in this category.

In this talk, I will discuss theoretical limitations of the lexicographic-leader approach to finding canonical forms.  It turns out that this approach leads to NP-complete problems, even for very restricted classes of graphs for which there are simple polynomial-time solutions by group-theoretic methods.

Comments are closed.


Places I've Been

The following links are virtual breadcrumbs marking the 12 most recent pages you have visited in Bucknell.edu. If you want to remember a specific page forever click the pin in the top right corner and we will be sure not to replace it. Close this message.