An output sensitive algorithm for computing a maximum independent set of a circle graph - GREGG, DAVID; NASH, NICHOLAS CONAL ANTHONY (My University, 2010)
We present an output sensitive algorithm for computing a maximum independent set of an unweighted circle graph. Our algorithm requires O(nmin{d,?}) time at worst, for an n vertex circle graph where ? is the independence number of the circle graph and d is its density. Previous algorithms for this problem required ?(nd) time at worst.
PUBLISHED
Keywords: Computer Science; Design of algorithms