@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.}
}