Geodesic
On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems
Yugoslav journal of operations research, Tome 21 (2011) no. 1, p. 11

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

In this paper we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance (a graph with $n$ vertices) is revealed in $t$ clusters, $2 \leq t \leq n$ . We first focus on an on-line version of the maximum- weighted hereditary subgraph problem. Then, we deal with the particular case of the independent set problem. We are interested in two types of results: the competitive ratio guaranteed by the on-line algorithm and hardness results that account for the difficulty of the problems and for the quality of algorithms developed to solve them.
Classification : 68Q25, 68W40, 90C27, 90C35
Keywords: On-line algorithms, hereditary property, independent set, competitive ratio. 
@article{YJOR_2011_21_1_a1,
     author = {Marc Demange and Bernard Kouakou and Eric Soutif},
     title = {On-Line {Computation} and {Maximum-Weighted} {Hereditary} {Subgraph} {Problems}},
     journal = {Yugoslav journal of operations research},
     pages = {11 },
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2011_21_1_a1/}
}
TY  - JOUR
AU  - Marc Demange
AU  - Bernard Kouakou
AU  - Eric Soutif
TI  - On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems
JO  - Yugoslav journal of operations research
PY  - 2011
SP  - 11 
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2011_21_1_a1/
LA  - en
ID  - YJOR_2011_21_1_a1
ER  - 
%0 Journal Article
%A Marc Demange
%A Bernard Kouakou
%A Eric Soutif
%T On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems
%J Yugoslav journal of operations research
%D 2011
%P 11 
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2011_21_1_a1/
%G en
%F YJOR_2011_21_1_a1
Marc Demange; Bernard Kouakou; Eric Soutif. On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems. Yugoslav journal of operations research, Tome 21 (2011) no. 1, p. 11 . http://geodesic.mathdoc.fr/item/YJOR_2011_21_1_a1/