After wading through a torrent of submissions, the ICALP programme committee released the final list of accepted papers this week. There are 126 in total, 70 in track A (last year: 76 and 41). It looks like over 20 papers a day are going to be jostling for attention in multiple parallel sessions.

A paper I found interesting is

Marc Tedder, Derek Corneil, Michel Habib and Christophe Paul. Simple, Linear-Time Modular Decomposition

This paper claims to be the first practical implementation of linear time modular decomposition, which is used as a building block by many efficient graph algorithms. Jens Gustedt pointed out a few years ago that the Ehrenfeucht et al. algorithm from 1994 seems to have runtime , which is slightly worse than linear. This certainly has been implemented, although I’m unsure if the bound Jens suggested is achieved by this code; Ross McConnell also mentioned a previous implementation (lost in the mists of time). Implementing the 1994 algorithm involves some fairly nontrivial bits, mostly in reconstructing missing `obvious’ details. I am therefore looking forward to reading the paper in detail — it would be nice to have an algorithm that can be implemented, and that still achieves linear runtime.

### Like this:

Like Loading...

*Related*

## ICALP 2008 accepted papers

Tags: conferences, papers

After wading through a torrent of submissions, the ICALP programme committee released the final list of accepted papers this week. There are 126 in total, 70 in track A (last year: 76 and 41). It looks like over 20 papers a day are going to be jostling for attention in multiple parallel sessions.

A paper I found interesting is

Marc Tedder, Derek Corneil, Michel Habib and Christophe Paul. Simple, Linear-Time Modular Decomposition

This paper claims to be the first practical implementation of linear time modular decomposition, which is used as a building block by many efficient graph algorithms. Jens Gustedt pointed out a few years ago that the Ehrenfeucht et al. algorithm from 1994 seems to have runtime , which is slightly worse than linear. This certainly has been implemented, although I’m unsure if the bound Jens suggested is achieved by this code; Ross McConnell also mentioned a previous implementation (lost in the mists of time). Implementing the 1994 algorithm involves some fairly nontrivial bits, mostly in reconstructing missing `obvious’ details. I am therefore looking forward to reading the paper in detail — it would be nice to have an algorithm that can be implemented, and that still achieves linear runtime.

## Like this:

Related