| dc.contributor.author | GREGG, DAVID | en |
| dc.contributor.author | NASH, NICHOLAS CONAL ANTHONY | en |
| dc.date.accessioned | 2010-06-08T14:22:15Z | |
| dc.date.available | 2010-06-08T14:22:15Z | |
| dc.date.issued | 2010 | en |
| dc.date.submitted | 2010 | en |
| dc.identifier.citation | 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-634 | en |
| dc.identifier.other | Y | en |
| dc.description | PUBLISHED | en |
| dc.description.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. | en |
| dc.format.extent | 630-634 | en |
| dc.language.iso | en | en |
| dc.relation.ispartofseries | Information Processing Letters | en |
| dc.relation.ispartofseries | 110 | en |
| dc.relation.ispartofseries | 16 | en |
| dc.rights | Y | en |
| dc.subject | Computer Science | en |
| dc.subject | Design of algorithms | en |
| dc.title | An output sensitive algorithm for computing a maximum independent set of a circle graph | en |
| dc.type | Journal Article | en |
| dc.type.supercollection | scholarly_publications | en |
| dc.type.supercollection | refereed_publications | en |
| dc.identifier.peoplefinderurl | http://people.tcd.ie/dgregg | en |
| dc.identifier.rssinternalid | 66780 | en |
| dc.identifier.rssuri | http://dx.doi.org/10.1016/j.ipl.2010.05.016 | en |
| dc.contributor.sponsor | Irish Research Council for Science and Engineering Technology (IRCSET) | en |
| dc.identifier.uri | http://hdl.handle.net/2262/40096 | |
