2010_Nash.pdf (198.64 kB)
An output sensitive algorithm for computing a maximum independent set of a circle graph
journal contribution
posted on 2012-05-30, 10:29 authored by Nicholas Nash, David GreggWe 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.
Funding
A new method for transforming data to normality with application to density estimation
National Research Foundation
Find out more...History
Publication
Information Processing Letters; 110(16), pp. 630-634Publisher
ElsevierNote
peer-reviewedOther Funding information
IRCSET, SFIRights
This is the author’s version of a work that was accepted for publication in Information Processing Letters. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Information Processing Letters 2010 110 (16), pp.630-634 DOIdoi.org/10.1016/j.ipl.2010.05.016,Language
EnglishExternal identifier
Usage metrics
Categories
No categories selectedLicence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC