# On-line models and algorithms for max independent set

Bruno Escoffier; Vangelis Th. Paschos

RAIRO - Operations Research (2006)

- Volume: 40, Issue: 2, page 129-142
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topEscoffier, Bruno, and Paschos, Vangelis Th.. "On-line models and algorithms for max independent set." RAIRO - Operations Research 40.2 (2006): 129-142. <http://eudml.org/doc/249628>.

@article{Escoffier2006,

abstract = {
In on-line computation, the instance of the problem dealt is not
entirely known from the beginning of the solution process, but it
is revealed step-by-step. In this paper we deal with on-line
independent set. On-line models studied until now for this problem
suppose that the input graph is initially empty and revealed
either vertex-by-vertex, or cluster-by-cluster. Here we present a
new on-line model quite different to the ones already studied. It
assumes that a superset of the final graph is initially present
(in our case the complete graph on the order n of the final
graph) and edges are progressively removed until the achievement
of the final graph. Next, we revisit the model introduced in
[Demange, Paradon and Paschos, Lect. Notes Comput. Sci.1963 (2000)
326–334] and study relaxations assuming that some
paying backtracking is allowed.
},

author = {Escoffier, Bruno, Paschos, Vangelis Th.},

journal = {RAIRO - Operations Research},

keywords = {Approximation algorithms; competitive ratio; maximum
independent set; on-line algorithms.; approximation algorithms; maximum independent set; on-line algorithms},

language = {eng},

month = {10},

number = {2},

pages = {129-142},

publisher = {EDP Sciences},

title = {On-line models and algorithms for max independent set},

url = {http://eudml.org/doc/249628},

volume = {40},

year = {2006},

}

TY - JOUR

AU - Escoffier, Bruno

AU - Paschos, Vangelis Th.

TI - On-line models and algorithms for max independent set

JO - RAIRO - Operations Research

DA - 2006/10//

PB - EDP Sciences

VL - 40

IS - 2

SP - 129

EP - 142

AB -
In on-line computation, the instance of the problem dealt is not
entirely known from the beginning of the solution process, but it
is revealed step-by-step. In this paper we deal with on-line
independent set. On-line models studied until now for this problem
suppose that the input graph is initially empty and revealed
either vertex-by-vertex, or cluster-by-cluster. Here we present a
new on-line model quite different to the ones already studied. It
assumes that a superset of the final graph is initially present
(in our case the complete graph on the order n of the final
graph) and edges are progressively removed until the achievement
of the final graph. Next, we revisit the model introduced in
[Demange, Paradon and Paschos, Lect. Notes Comput. Sci.1963 (2000)
326–334] and study relaxations assuming that some
paying backtracking is allowed.

LA - eng

KW - Approximation algorithms; competitive ratio; maximum
independent set; on-line algorithms.; approximation algorithms; maximum independent set; on-line algorithms

UR - http://eudml.org/doc/249628

ER -

## References

top- G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie and M. Talamo, Algorithms for the on-line traveling salesman problem. Algorithmica29 (2001) 560–581.
- C. Berge, Graphs and hypergraphs. North Holland, Amsterdam (1973).
- M. Demange, X. Paradon and V.Th. Paschos, On-line maximum-order induced hereditary subgraph problems, in SOFSEM 2000—Theory and Practice of Informatics, edited by V. Hlaváč, K.G. Jeffery and J. Wiedermann. Springer-Verlag, Lect. Notes Comput. Sci.1963 (2000) 326–334.
- M. Demange, V.Th. Paschos, Improved approximations for maximum independent set via approximation chains. Appl. Math. Lett.10 (1997) 105–110.
- M. Demange, V.Th. Paschos, Improved approximations for weighted and unweighted graph problems. Theor. Comput. Syst. To appear.
- B. Escoffier, Problème on-line du stable de cardinalité maximale. Mémoire de DEA (2002).
- M.M. Halldórsson, Approximations via partitioning. JAIST Research Report IS-RR-95-0003F, Japan Advanced Institute of Science and Technology, Japan (1995).
- M.M. Halldórsson, Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Appli.4 (2000) 1–16.
- M.M. Halldórsson, K. Iwama, S. Miyazaki and S. Taketomi, Online independent sets. Theoret. Comput. Sci.289 (2002) 953–962.
- D.S. Hochbaum, editor, Approximation algorithms for NP-hard problems. PWS, Boston (1997).
- V.Th. Paschos, A survey about how optimal solutions to some covering and packing problems can be approximated. ACM Comput. Surveys29 (1997) 171–209.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.