×

On-line vertex-covering. (English) Zbl 1070.68118

Summary: We study the minimum vertex-covering problem under two on-line models corresponding to two different ways vertices are revealed. The former one implies that the input-graph is revealed vertex-by-vertex. The second model implies that the input-graph is revealed per clusters, i.e. per induced subgraphs of the final graph. Under the cluster-model, we then relax the constraint that the choice of the part of the final solution dealing with each cluster has to be irrevocable, by allowing backtracking. We assume that one can change decisions upon a vertex membership of the final solution, this change implying, however, some cost depending on the number of the vertices changed.

MSC:

68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ausiello, G.; Feuerstein, E.; Leonardi, S.; Stougie, L.; Talamo, M., Algorithms for the on-line traveling salesman problem, Algorithmica, 29, 4, 560-581 (2001) · Zbl 0985.68088
[2] Bar-Yehuda, R.; Even, S., A local-ratio theorem for approximating the weighted vertex cover problem, Ann. Discrete Appl. Math., 25, 27-46 (1985) · Zbl 0557.90072
[3] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[4] M. Demange, X. Paradon, V. T. Paschos, On-line maximum-order induced hereditary subgraph problems, in: V. Hlaváč, K.G. Jeffery, J. Wiedermann (Eds.), SOFSEM 2000—Theory and Practice of Informatics, Lecture Notes in Computer Science, Vol. 1963, Springer, Berlin, 2000, pp. 326-334.; M. Demange, X. Paradon, V. T. Paschos, On-line maximum-order induced hereditary subgraph problems, in: V. Hlaváč, K.G. Jeffery, J. Wiedermann (Eds.), SOFSEM 2000—Theory and Practice of Informatics, Lecture Notes in Computer Science, Vol. 1963, Springer, Berlin, 2000, pp. 326-334. · Zbl 1043.68615
[5] R. El-Yaniv, A. Fiat, R.E. Karp, G.Turpin, Competitive analysis of financial games, in: Proc. FOCS’92, 1992, pp. 327-333.; R. El-Yaniv, A. Fiat, R.E. Karp, G.Turpin, Competitive analysis of financial games, in: Proc. FOCS’92, 1992, pp. 327-333. · Zbl 0977.68504
[6] A. Fiat, G. Wœginger (Eds.), Online Algorithms: The State of the Art, Lecture Notes in Computer Science, Vol. 1442, Springer, Berlin, 1998.; A. Fiat, G. Wœginger (Eds.), Online Algorithms: The State of the Art, Lecture Notes in Computer Science, Vol. 1442, Springer, Berlin, 1998. · Zbl 1177.68009
[7] Gyárfás, A.; Lehel, J., Online and first-fit colorings of graphs, J. Graph Theory, 12, 217-227 (1988) · Zbl 0657.05026
[8] Halldórsson, M. M.; Iwama, K.; Miyazaki, S.; Taketomi, S., Online independent sets, Theoret. Comput. Sci., 289, 2, 953-962 (2002) · Zbl 1061.68187
[9] Halldórsson, M. M.; Szegedy, M., Lower bounds for on-line graph coloring, Theoret. Comput. Sci., 130, 1, 163-174 (1994) · Zbl 0822.68081
[10] Irani, S.; Karlin, A. R., Online computation, (Hochbaum, D. S., Approximation Algorithms for NP-hard Problems (1997), PWS Publishing Company: PWS Publishing Company MA), 521-565, (Chapter 13)
[11] Lovász, L.; Saks, M.; Trotter, W., An on-line graph coloring algorithm with sublinear performance ratio, Discrete Math., 75, 1-3, 319-325 (1989) · Zbl 0679.05031
[12] Papadimitriou, C. H.; Steiglitz, K., Combinatorial OptimizationAlgorithms and Complexity (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[13] Sleator, D.; Tarjan, R. E., Amortized efficiency of list update and paging rules, Commun. ACM, 28, 2, 202-208 (1985)
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.