An output sensitive algorithm for computing a maximum independent set of a circle graph
![Thumbnail](/themes/edepositireland/images/white_rectangle.jpeg)
File Type:
PDFItem Type:
Journal ArticleDate:
2010Citation:
Nicholas Nash, David Gregg, An output sensitive algorithm for computing a maximum independent set of a circle graph, Information Processing Letters, 110, 16, 2010, 630-634Download Item:
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.
Sponsor
Grant Number
Irish Research Council for Science and Engineering Technology (IRCSET)
Author's Homepage:
http://people.tcd.ie/dgreggDescription:
PUBLISHED
Author: GREGG, DAVID; NASH, NICHOLAS CONAL ANTHONY
Sponsor:
Irish Research Council for Science and Engineering Technology (IRCSET)Type of material:
Journal ArticleCollections
Series/Report no:
Information Processing Letters110
16
Availability:
Full text availableKeywords:
Computer Science, Design of algorithmsMetadata
Show full item recordLicences: