• français
    • English
  • français 
    • français
    • English
  • Connexion
JavaScript is disabled for your browser. Some features of this site may not work without it.
Accueil

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

On-line independent set by coloring vertices

Thumbnail
Date
2001
Indexation documentaire
Recherche opérationnelle
Subject
Independent set; Coloring; Approximation algorithm; On-line computation
Nom de la revue
Operational Research
Volume
1
Numéro
3
Date de publication
09-2001
Pages article
213-224
Nom de l'éditeur
Springer
DOI
http://dx.doi.org/10.1007/BF02936352
URI
https://basepub.dauphine.fr/handle/123456789/3835
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Paschos, Vangelis
Type
Article accepté pour publication ou publié
Résumé en anglais
In on-line computation, the instance of a problem is revealed step-by-step and one has, at the end of each step, to irrevocably decide on the part of the final solution dealing with this step. In this paper, we study the on-line independent set under a model assuming that the input graph G is revealed by non-empty clusters, i.e., by induced subgraphs of G. We suppose that the order of the graph, as well as the number of clusters needed so that the whole of the graph is revealed are a priori known. The algorithm we propose implies approximation of the vertex-coloring problem in each cluster. We first establish a general result for the competitivity of the method studied. Next, we restrict ourselves in natural and well-known independent set sub-problems and perform a precise evaluation of the competitivity ratio of our algorithm for the sub-problems considered.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Cette création est mise à disposition sous un contrat Creative Commons.