@InProceedings{ valiente:lncs:2906:2003,
author = {Gabriel Valiente},
booktitle = {Proc.\ 14th Ann.\ Int.\ Symp.\ Algorithms and Computation},
pages = {126--135},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
title = {A New Simple Algorithm for the Maximum-Weight Independent
Set Problem on Circle Graphs},
volume = {2906},
year = {2003},
abstract = {The problem of finding an independent set of maximum
weight for the chord model of a circle graph is solved in
$O(\ell)$ time and $O(n)$ space, where $n$ is the number of
vertices and $\ell$ is the total chord length of the circle
graph. The best previous algorithm required $O(dn)$ time
and space, where $d$ is the maximum number of intervals
crossing any position on the line in the interval model of
the graph. The algorithm is practical, requires only simple
data structures to be implemented within the stated time
and space bounds, and has small hidden constants.}
}