Thumbnail
Access Restriction
Subscribed

Author Nash, Nicholas ♦ Lelait, Sylvain ♦ Gregg, David
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Circle graph ♦ Maximum independent set ♦ Maximum stable set
Abstract Circle graphs are an important class of graph with applications in a number of areas, including compiler optimization, VLSI design and computational geometry. In this article, we provide an experimental evaluation of the two most efficient algorithms for computing the maximum independent set of a circle graph. We provide details of our implementations of the algorithms of Apostolico et al. and Valiente [2003], together with time, space, and other measurements. We describe optimizations to the algorithm of Apostolico et al. that significantly reduce both its running time and its memory consumption. We also correct an error in this algorithm. In addition, we show how to restructure and simplify Valiente's algorithm, allowing us to remove redundant computations from the algorithm resulting in much improved performance. Moreover, in the case of both algorithms, when the density of the circle graph's associated interval representation is increased beyond a certain point the efficacy of the optimizations we apply increases dramatically and as a function of the density. We provide experimental results over dense and sparse random circle graphs, as well as for circle graphs that arise when performing register allocation of software pipelined loops in a compiler.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2009-02-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 13
Page Count 26
Starting Page 1.9
Ending Page 1.34


Open content in new tab

   Open content in new tab
Source: ACM Digital Library