×

On-line maximum-order induced hereditary subgraph problems. (English) Zbl 1063.90059

Summary: We first study the competitive 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. Next, we focus ourselves on two of the most known instantiations of this problem: the maximum independent set and the maximum clique. Finally, we study a variant of the on-line maximum-weight induced hereditary subgraph problem. Our results can also be seen as general reductions, either from off-line problems to the corresponding on-line versions, or between on-line problems. The concept of reduction was absent, until now, from the on-line computation.

MSC:

90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] DOI: 10.1007/s004530010071 · Zbl 0985.68088 · doi:10.1007/s004530010071
[2] Boppana B.B., BIT Numerical Mathematics 32 (2) pp 180– (1992)
[3] Demange M., Yugoslavia Journal of Operations Research 13 (1) pp 3– (2003)
[4] Demange M., SOFSEM 2000-Theory and Practice of Informatics. Lecture Notes in Computer Science 1963 pp 326– (2000)
[5] M. Demange, and V.Th. Paschos , 1999 . Maximum-weight independent set is as ’well-approximated’ as the unweighted one.Cahier du LAMSADE 163, LAMSADE, Universite Paris-Dauphine, June 1999.
[6] M. Demange, and V.Th. Paschos , 2001 . On-line vertex-covering.Cahier du LAMSADE 183, LAMSADE, Universite Paris-Dauphine. Available onhttp://www.lamsade.dauphine.fr/cahdoc.html#cahiers · Zbl 1070.68118
[7] Demange M., Proceedings of the 28th International Workshop on Graph Theoretical Concepts in Computer Science, WG’02. Lecture Notes in Computer Science 2573 pp 102– (2002) · doi:10.1007/3-540-36379-3_10
[8] B. Escoffier, and V.Th. Paschos , 2004 . On-line models and algorithms formax independent set.Annales du LAMSADE 2, LAMSADE, Universite Paris-Dauphine. Available onhttp://www.lamsade.dauphine.fr/cahdoc.html#cahiers. · Zbl 1110.68170
[9] Fiat A., Online Algorithms: The State of the Art. Lecture Notes in Computer Science 1442 (1998) · Zbl 1177.68009
[10] Gyarfas A., Journal of Graph Theory 12 pp 217– (1988)
[11] M.M. Halldorsson , 1995 . Approximations via partitioning.JAIST Research Report IS-RR-95-0003F, Japan Advanced Institute of Science and Technology, Japan.
[12] Halldorsson M.M., Proceedings of the Fifth Annual International Conference on Computing and Combinatorics. Lecture Notes in Computer Science pp 261– (1999)
[13] Halldorsson M.M., Electronic Journal of Combinatorics 7 (2000)
[14] DOI: 10.1016/S0304-3975(01)00411-X · Zbl 1061.68187 · doi:10.1016/S0304-3975(01)00411-X
[15] DOI: 10.1016/0304-3975(94)90157-0 · Zbl 0822.68081 · doi:10.1016/0304-3975(94)90157-0
[16] Irani S., Approximation Algorithms for NP-Hard Problems pp 521– (1997)
[17] DOI: 10.1016/0012-365X(89)90096-4 · Zbl 0679.05031 · doi:10.1016/0012-365X(89)90096-4
[18] Sleator D., Commununications of the Association for Computing Machinery 28 (2) pp 202– (1985) · doi:10.1145/2786.2793
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.