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

tm0

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.

Close

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.