An output sensitive algorithm for computing a maximum independent set of a circle graph |
| |
| Authors: | Nicholas Nash David Gregg |
| |
| Affiliation: | a Dept. of Computer Science, Trinity College, Dublin, Ireland
b Lero, Trinity College, Dublin, Ireland |
| |
| 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. |
| |
| Keywords: | Design of algorithms Graph algorithms Circle graph Maximum independent set Maximum stable set |
| 本文献已被 ScienceDirect 等数据库收录！ |
