Constraints

14 April 2008

ICALP 2008 accepted papers

Filed under: Commentary — András Salamon @ 14:52
Tags: ,

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 \min(n^2,m \log n), 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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: