The Taub Faculty of Computer Science Events and Talks
Prajakta Nimbhorkar (The Institute of Mathematical Sciences)
Wednesday, 19.08.2009, 15:00
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
Joint work with:
Samir Datta, Nutan Limaye, Thomas Thierauf and Fabian Wagner.