Theoretical Computer Science Group

Theory Seminar Schedule for Spring 2017

The weekly Theory seminar provides an opportunity to get exposed to cutting edge research in theoretical computer science, to learn to understand technical material from talks and to give technical presentations. Graduate students interested in doing research in algorithms, complexity theory, cryptography, quantum computing and related areas are strongly encouraged to attend.

DateSpeakerTitle
January 20 Martin Furer (PSU) Multi-Clique-Width, a Powerful New Width Parameter
January 27 TBD TBD
February 3 TBD TBD
February 10 TBD TBD
February 17 TBD TBD
February 24 TBD TBD
March 3 TBD TBD
March 10 TBD TBD
March 17 TBD TBD
March 24 TBD TBD
March 31 TBD TBD
Archives

Spring 2007     Fall 2007     Spring 2008     Summer 2008     Fall 2008     Spring 2009     Fall 2009     Spring 2010     Fall 2010     Spring 2011     Fall 2011     Spring 2012     Fall 2012     Spring 2013     Fall 2013     Fall 2014     Spring 2015     Fall 2015     Spring 2016     Fall 2016



Multi-Clique-Width, a Powerful New Width Parameter

Multi-clique-width is a width parameter for graphs. It is obtained by a simple modification in the definition of clique-width. It has the advantage of providing a natural extension of tree-width. Unlike clique-width, it does not explode exponentially compared to tree-width. Efficient algorithms based on multi-clique-width are still possible for interesting tasks like computing the size of a maximum independent set (or even the independent set polynomial) or computing the chromatic number. For these tasks, the running time as a function of the multi-clique-width is the same as the running time of the fastest known algorithm as a function of the clique-width. This results in an exponential speed-up for some graphs, if the corresponding graph generating expressions are given. The reason is that the multi-clique-width is never bigger, but is exponentially smaller than the clique-width for many graphs.

Tree-width and clique-width will be introduced.

Based on the ITCS 2017 paper: "Multi-Clique-Width."