Thumbnail Image
Publication

An output sensitive algorithm for computing a maximum independent set of a circle graph

Date
2010
Abstract
We present an output sensitive algorithm for computing a maximum independent set of an unweighted circle graph. Our algorithm requires O(n min{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.
Supervisor
Description
peer-reviewed
Publisher
Elsevier
Citation
Information Processing Letters; 110(16), pp. 630-634
Collections
Lero - The Science Foundation Ireland Research Centre for Software
Show all metadata
Files
Thumbnail Image
2010_Nash.pdf
Adobe PDF, 198.64 KB
Keywords
computer science, design of algorithms
ULRR Identifiers
https://hdl.handle.net/10344/2228
 https://doi.org/10.34961/837
Funding code
Funding Information
Irish Research Council for Science, Engineering and Technology (IRCSET), Science Foundation Ireland (SFI)
Sustainable Development Goals
External Link
Type
Article
Rights
https://creativecommons.org/licenses/by-nc-sa/1.0/
License