Centre d'Etude et De Recherche en Informatique et Communications (EA4629) |
|
On-line computation and maximum-weighted hereditary subgrah problems
[DKS11] On-line computation and maximum-weighted hereditary subgrah problems
Revue Internationale avec comité de lecture : Journal yugoslav Journal of Operations Research, vol. 21(1), pp. 11-28 , 2011, (doi:10.2298/YJOR1101011D)
motcle:
Résumé:
In this paper1 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 ≤ t ≤ n . We first focus on an on-line version of the maximumweighted
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.
Equipe:
oc
| @article { | |||
| DKS11, | |||
| title | = | "{On-line computation and maximum-weighted hereditary subgrah problems}", | |
| author | = | "M. Demange and B. Kouakou and E. Soutif", | |
| journal | = | "yugoslav Journal of Operations Research", | |
| year | = | 2011, | |
| volume | = | 21, | |
| number | = | 1, | |
| pages | = | "11-28 ", | |
| doi | = | "10.2298/YJOR1101011D", | |
| } | |||
Agenda
 Suivre le laboratoire
|
ContactsCNAM-CEDRIC ENSIIE-CEDRIC |