Seminar by Dr. Narayan Vikas
Computational Complexity of Graph Compaction
Dr. Narayan Vikas
Technology, Research and Development Division (Applied Technology Group)
Tata Infotech Limited
India
Date: Friday, May 16, 2003
Time: 3:45 PM
Venue: CS-101
Abstract
In this talk, we shall present various complexity results for the graph compaction problem which is a special graph colouring problem. In particular, we present solution to a widely publicised open problem posed by Winkler in 1988. We also present results for some other problems that have been of interest since a long time. We shall also show a very close relationship between the compaction problem and the constraint satisfaction problem. The constraint satisfaction problem is of great interest in artificial intelligence. Some research problems will also be discussed.