On-line maximum-order induced hereditary subgraph problems

Demange, Marc; Paradon, Xavier; Paschos, Vangelis

Demange, Marc; Paradon, Xavier; Paschos, Vangelis (2000), On-line maximum-order induced hereditary subgraph problems, in Hlavac, Vaclav; Jeffery, Keith G.; Wiedermann, Jiri, SOFSEM 2000: Theory and Practice of Informatics SOFSEM 2000: Theory and Practice of Informatics 27th Conference on Current Trends in Theory and Practice of Informatics Milovy, Czech Republic, November 25 - December 2, 2000 Proceedings, Springer : Berlin, p. 327-335. http://dx.doi.org/10.1007/3-540-44411-4_21

Type

Communication / Conférence

Date

2000

Conference title

27th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM'00)

Conference date

2000-11

Conference city

Milovy

Conference country

République tchèque

Book title

SOFSEM 2000: Theory and Practice of Informatics SOFSEM 2000: Theory and Practice of Informatics 27th Conference on Current Trends in Theory and Practice of Informatics Milovy, Czech Republic, November 25 - December 2, 2000 Proceedings

Book author

Hlavac, Vaclav; Jeffery, Keith G.; Wiedermann, Jiri

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

1963

Published in

Berlin

ISBN

978-3-540-41348-6

Number of pages

460

Pages

327-335

Abstract (EN)

We first study the competitivity ratio for the on-line version of the problem of finding a maximum-order induced subgraph satisfying some hereditary property, under the hypothesis that the input graph is revealed by clusters. Then, we focus ourselves on two of the most known instantiations of this problem, the maximum independent set and the maximum clique.

Subjects / Keywords

Approximation algorithms; On-line algorithms; Maximum independent set; Competitive ratio