דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: A log-space algorithm for planar graph isomorphism
event speaker icon
Prajakta Nimbhorkar (The Institute of Mathematical Sciences)
event date icon
יום רביעי, 19.8.2009, 15:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
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.

Joint work with: Samir Datta, Nutan Limaye, Thomas Thierauf and Fabian Wagner.
[בחזרה לאינדקס האירועים]