Thumbnail - Request a copy

On-line maximum-order induced hereditary subgraph problems

Demange, Marc; Paradon, Xavier; Paschos, Vangelis (2000), On-line maximum-order induced hereditary subgraph problems, dans Hlavac, Vaclav; Jeffery, Keith G.; Wiedermann, Jiri, SOFSEM 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 Proceedings, Springer : Berlin, p. 327-335. http://dx.doi.org/10.1007/3-540-44411-4_21

Type
Communication / Conférence
Date
2000
Titre du colloque
27th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM'00)
Date du colloque
2000-11
Ville du colloque
Milovy
Pays du colloque
République tchèque
Titre de l'ouvrage
SOFSEM 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 Proceedings
Auteurs de l’ouvrage
Hlavac, Vaclav; Jeffery, Keith G.; Wiedermann, Jiri
Éditeur
Springer
Titre de la collection
Lecture Notes in Computer Science
Numéro dans la collection
1963
Ville d’édition
Berlin
Isbn
978-3-540-41348-6
Nombre de pages
460
Pages
327-335
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Demange, Marc
Paradon, Xavier
Paschos, Vangelis
Résumé (EN)
We 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.
Mots-clés
Approximation algorithms; On-line algorithms; Maximum independent set; Competitive ratio