|
 
|
[DKS05] On-line computation and maximum-weighted hereditary
Conférence Internationale avec comité de lecture : ISAAC'05, 16th Annual Int. Symp. on Algorithms and Computation, Sanya, Hainan, China, January 2005,
motcle:
Résumé:
In this paper, we study the on-line version of maximum-weighted
hereditary subgraph problems. In our on-line model, the final
instance-graph (which has n vertices) is revealed in t
clusters, 2 <= t <= n. We first focus on the on-line version
of the following problem: finding a maximum-weighted subgraph
satisfying some hereditary property. Then, we deal with the
particular case of the independent set. For all these problems, we
are interested in two types of results: the competitivity 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.
Collaboration:
BibTeX
| @inproceedings { | |||
| DKS05, | |||
| title | = | "{On-line computation and maximum-weighted hereditary}", | |
| author | = | " M. Demange and B. Kouakou and E. Soutil ", | |
| booktitle | = | "{ISAAC'05, 16th Annual Int. Symp. on Algorithms and Computation, Sanya, Hainan, China}", | |
| year | = | 2005, | |
| month | = | "January", | |
| } | |||
