• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

On-line independent set by coloring vertices

Paschos, Vangelis (2001), On-line independent set by coloring vertices, Operational Research, 1, 3, p. 213-224. http://dx.doi.org/10.1007/BF02936352

Type
Article accepté pour publication ou publié
Date
2001
Journal name
Operational Research
Volume
1
Number
3
Publisher
Springer
Pages
213-224
Publication identifier
http://dx.doi.org/10.1007/BF02936352
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Abstract (EN)
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.
Subjects / Keywords
Independent set; Coloring; Approximation algorithm; On-line computation

Related items

Showing items related by title and author.

  • Thumbnail
    Solving on line independent set by coloring vertices 
    Paschos, Vangelis; Veslot, Hélène (2001) Communication / Conférence
  • Thumbnail
    On-line models and algorithms for max independent set 
    Paschos, Vangelis; Escoffier, Bruno (2006) Article accepté pour publication ou publié
  • Thumbnail
    Maximum independent set and linear programming 
    Demange, Marc; Paschos, Vangelis (1995) Communication / Conférence
  • Thumbnail
    Greedy algorithms for on-line set-covering 
    Bourgeois, Nicolas; Ausiello, Giorgio; Paschos, Vangelis; Giannakos, Aristotelis (2009) Article accepté pour publication ou publié
  • Thumbnail
    Greedy algorithms for on-line set-covering and related problems 
    Ausiello, Giorgio; Giannakos, Aristotelis; Paschos, Vangelis (2006) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo