[CCICADA-announce] DIMACS/CCICADA Interdisciplinary Seminar Series - Monday, February 24, 2014

[Linda Casals]

****************REMINDER*******************REMINDER******************
*********************************************************************

DIMACS/CCICADA Interdisciplinary Seminar Series Presents
               
*********************************************************************

Title: The Isomorphism Problem for k-trees is Complete for Logspace

Speaker: Bireswar Das, IUSSTF Research Fellow-DIMACS

Date: Monday**, February 24, 2014 11:00am - 12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University                 
             Busch Campus, Piscataway, NJ

**Note special day             
*********************************************************************

The Graph Isomorphism problem (GI) has received considerable attention
since it is one of the few natural problems in NP that are neither
known to be NP-complete nor known to be solvable in polynomial
time. Though the complexity status of this problem for general graphs
remains unknown, several efficient algorithms are known for restricted
classes of graphs. In this talk we show that, for k constant, k-tree
isomorphism can be decided in logarithmic space by giving an O(k log
n) space algorithm. We also prove that k-tree isomorphism is complete
for logspace. We show that the automorphism problem and the
canonization problem from k-trees are also in deterministic
logspace. 

This is a joint work with V. Arvind, J. Koebler, S. Kuhnert.

DIMACS/CCICADA Interdisciplinary Series 
See: http://dimacs.rutgers.edu/Seminars/interseminars13-14.html