University of Limerick Institutional Repository

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

DSpace/Manakin Repository

Show simple item record

dc.contributor.author Nash, Nicholas
dc.contributor.author Gregg, David
dc.date.accessioned 2012-05-30T10:29:49Z
dc.date.available 2012-05-30T10:29:49Z
dc.date.issued 2010
dc.identifier.citation Nash,N. (2010) "An output sensitive algorithm for computing a maximum independent set of a circle graph," Information Processing Letters 110 (16),pp. 630-634 en_US
dc.identifier.uri http://hdl.handle.net/10344/2228
dc.description peer-reviewed en_US
dc.description.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. en_US
dc.language.iso eng en_US
dc.publisher Elsevier en_US
dc.relation.ispartofseries Information Processing Letters; 110(16), pp. 630-634
dc.relation.uri http://dx.doi.org/ 10.1016/j.ipl.2010.05.016
dc.rights 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, en_US
dc.subject computer science en_US
dc.subject design of algorithms en_US
dc.title An output sensitive algorithm for computing a maximum independent set of a circle graph en_US
dc.type info:eu-repo/semantics/article en_US
dc.type.supercollection all_ul_research en_US
dc.type.supercollection ul_published_reviewed en_US
dc.contributor.sponsor IRCSET en_US
dc.contributor.sponsor SFI
dc.rights.accessrights info:eu-repo/semantics/openAccess en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Related Items

Search DSpace


Advanced Search

Browse

My Account