• 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

On-line vertex-covering

Demange, Marc; Paschos, Vangelis (2005), On-line vertex-covering, Theoretical Computer Science, 332, 1-3, p. 83-108. http://dx.doi.org/10.1016/j.tcs.2004.08.015

View/Open
publi128.pdf (444.1Kb)
Type
Article accepté pour publication ou publié
Date
2005
Journal name
Theoretical Computer Science
Volume
332
Number
1-3
Publisher
Elsevier
Pages
83-108
Publication identifier
http://dx.doi.org/10.1016/j.tcs.2004.08.015
Metadata
Show full item record
Author(s)
Demange, Marc
Paschos, Vangelis
Abstract (EN)
We study the minimum vertex-covering problem under two on-line models corresponding to two different ways vertices are revealed. The former one implies that the input-graph is revealed vertex- by-vertex. The second model implies that the input-graph is revealed per clusters, i.e. per induced subgraphs of the final graph. Under the cluster-model, we then relax the constraint that the choice of the part of the final solution dealing with each cluster has to be irrevocable, by allowing backtracking. We assume that one can change decisions upon a vertex membership of the final solution, this change implying, however, some cost depending on the number of the vertices changed.
Subjects / Keywords
Graph; Vertex-covering; Competitive ratio; On-line algorithm

Related items

Showing items related by title and author.

  • Thumbnail
    On-line maximum-order induced hereditary subgraph problems 
    Paschos, Vangelis; Demange, Marc; Paradon, Xavier (2005) Article accepté pour publication ou publié
  • Thumbnail
    Algorithms for the on-line quota traveling salesman problem 
    Ausiello, Giorgio; Demange, Marc; Laura, Luigi; Paschos, Vangelis (2004) Article accepté pour publication ou publié
  • Thumbnail
    Algorithms for the on-line quota traveling salesman problem 
    Ausiello, Giorgio; Demange, Marc; Laura, Luigi; Paschos, Vangelis (2004) Communication / Conférence
  • Thumbnail
    On-line maximum-order induced hereditary subgraph problems 
    Demange, Marc; Paradon, Xavier; Paschos, Vangelis (2000) 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é
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