Show icon Show search tips...
Hide icon Hide search tips...

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

Linda Casals lindac at
Mon Feb 24 08:56:37 EST 2014


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

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

DIMACS/CCICADA Interdisciplinary Series 

More information about the Dimacs-ccicada-announce mailing list