|
 
|
[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
Collaboration:
BibTeX
| @article { | |||
| DKS11, | |||
| title | = | "{On-line computation and maximum-weighted hereditary subgrah problems}", | |
| author | = | "M. Demange and B. Kouakou and E. Soutil", | |
| journal | = | "yugoslav Journal of Operations Research", | |
| year | = | 2011, | |
| volume | = | 21, | |
| number | = | 1, | |
| pages | = | "11-28 ", | |
| doi | = | "10.2298/YJOR1101011D", | |
| } | |||
