Show simple item record

On-line maximum-order induced hereditary subgraph problems

dc.contributor.authorDemange, Marc
dc.contributor.authorParadon, Xavier
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2011-04-05T10:34:01Z
dc.date.available2011-04-05T10:34:01Z
dc.date.issued2000
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5903
dc.language.isoenen
dc.subjectApproximation algorithmsen
dc.subjectOn-line algorithmsen
dc.subjectMaximum independent seten
dc.subjectCompetitive ratioen
dc.subject.ddc003en
dc.titleOn-line maximum-order induced hereditary subgraph problemsen
dc.typeCommunication / Conférence
dc.description.abstractenWe first study the competitivity ratio for the on-line version of the problem of finding a maximum-order induced subgraph satisfying some hereditary property, under the hypothesis that the input graph is revealed by clusters. Then, we focus ourselves on two of the most known instantiations of this problem, the maximum independent set and the maximum clique.en
dc.identifier.citationpages327-335en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber1963
dc.relation.ispartoftitleSOFSEM 2000: Theory and Practice of Informatics SOFSEM 2000: Theory and Practice of Informatics 27th Conference on Current Trends in Theory and Practice of Informatics Milovy, Czech Republic, November 25 - December 2, 2000 Proceedingsen
dc.relation.ispartofeditorHlavac, Vaclav
dc.relation.ispartofeditorJeffery, Keith G.
dc.relation.ispartofeditorWiedermann, Jiri
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2000
dc.relation.ispartofpages460en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/3-540-44411-4en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-41348-6en
dc.relation.conftitle27th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM'00)en
dc.relation.confdate2000-11
dc.relation.confcityMilovyen
dc.relation.confcountryRépublique tchèqueen
dc.identifier.doihttp://dx.doi.org/10.1007/3-540-44411-4_21


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record