| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429077 | Information Processing Letters | 2010 | 5 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
