dc.contributor.author Bourgeois, Nicolas dc.contributor.author Escoffier, Bruno HAL ID: 5124 dc.contributor.author Paschos, Vangelis dc.date.accessioned 2010-09-13T10:42:52Z dc.date.available 2010-09-13T10:42:52Z dc.date.issued 2010 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/4757 dc.language.iso en en dc.subject Exact Algorithms en dc.subject Max Independent Set en dc.subject Bottom-Up Method en dc.subject.ddc 003 en dc.title A Bottom-Up Method and Fast Algorithms for max independent set en dc.type Communication / Conférence dc.description.abstracten We first propose a new method, called “bottom-up method”, that, informally, “propagates” improvement of the worst-case complexity for “sparse” instances to “denser” ones and we show an easy though non-trivial application of it to the min set cover problem. We then tackle max independent set. Following the bottom-up method we propagate improvements of worst-case complexity from graphs of average degree d to graphs of average degree greater than d. Indeed, using algorithms for max independent set in graphs of average degree 3, we tackle max independent set in graphs of average degree 4, 5 and 6. Then, we combine the bottom-up technique with measure and conquer techniques to get improved running times for graphs of maximum degree 4, 5 and 6 but also for general graphs. The best computation bounds obtained for max independent set are O *(1.1571 n ), O *(1.1918 n ) and O *(1.2071 n ), for graphs of maximum (or more generally average) degree 4, 5 and 6 respectively, and O *(1.2127 n ) for general graphs. These results improve upon the best known polynomial space results for these cases. en dc.identifier.citationpages 62-73 en dc.relation.ispartofseriestitle Lecture Notes in Computer Science dc.relation.ispartofseriesnumber 6139 dc.relation.ispartoftitle 12th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings en dc.relation.ispartofeditor Kaplan, Haim dc.relation.ispartofpublname Springer en dc.relation.ispartofpublcity Berlin en dc.relation.ispartofdate 2010 dc.relation.ispartofpages 450 en dc.relation.ispartofurl http://dx.doi.org/10.1007/978-3-642-13731-0 en dc.relation.isversionofdoi http://dx.doi.org/10.1007/978-3-642-13731-0_7 dc.description.sponsorshipprivate oui en dc.subject.ddclabel Recherche opérationnelle en dc.relation.ispartofisbn 978-3-642-13730-3 en dc.relation.conftitle 12th Scandinavian Symposium and Workshops on Algorithm Theory - SWAT'10 en dc.relation.confdate 2010-06 dc.relation.confcity Bergen en dc.relation.confcountry Norvège en
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.