Campus Event Calendar
Event Entry
New for: D1
What and Who
A log-space algorithm for planar graph isomorphism
Prajakta Nimbhorkar
Institute of Mathematical Sciences, Chennai, India
Talk
Prajakta is a Ph.D. and guest of AG1 until June, 27th.
AG 1
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 18 June 2009
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Graph isomorphism is an important problem and has received lot of attention over several years. Its complexity is still open. There have
been polynomial-time algorithms for several subclasses of graphs, including planar graphs. For isomorphism of some of these graph classes, the focus has been on determining the parallel complexity. The goal has been to show the isomorphism problem for various graph classes to be complete for some natural complexity class.
For planar graph isomorphism, the log-space lower bound was known, and
there has been a wide gap between the upper and lower bounds. Our result closes this gap by giving an upper bound which matches the lower bound. Thus it settles the complexity of planar graph isomorphism by giving a log-space algorithm.
been polynomial-time algorithms for several subclasses of graphs, including planar graphs. For isomorphism of some of these graph classes, the focus has been on determining the parallel complexity. The goal has been to show the isomorphism problem for various graph classes to be complete for some natural complexity class.
For planar graph isomorphism, the log-space lower bound was known, and
there has been a wide gap between the upper and lower bounds. Our result closes this gap by giving an upper bound which matches the lower bound. Thus it settles the complexity of planar graph isomorphism by giving a log-space algorithm.
Contact
Daniel Johannsen
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
isomorphism; planar graphs; log-space
Daniel Johannsen, 06/18/2009 11:39
Daniel Johannsen, 06/15/2009 20:59 -- Created document.
Daniel Johannsen, 06/15/2009 20:59 -- Created document.