Geodesic
On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems
Yugoslav journal of operations research, Tome 21 (2011) no. 1, p. 11 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

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 },
     year = {2011},
     volume = {21},
     number = {1},
     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
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
%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/