Loading...
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
Files
Loading...
2010_Nash.pdf
Adobe PDF, 198.64 KB
Keywords
ULRR Identifiers
Funding code
Funding Information
Irish Research Council for Science, Engineering and Technology (IRCSET), Science Foundation Ireland (SFI)