An approximation algorithm for the total covering problem
Pooya Hatami
Discussiones Mathematicae Graph Theory, Tome 27 (2007), p. 553-558 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

We introduce a 2-factor approximation algorithm for the minimum total covering number problem.

Publié le : 2007-01-01
EUDML-ID : urn:eudml:doc:270525 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1380,
     author = {Pooya Hatami},
     title = {An approximation algorithm for the total covering problem},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {27},
     year = {2007},
     pages = {553-558},
     zbl = {1142.05060},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1380}
}

Pooya Hatami. An approximation algorithm for the total covering problem. Discussiones Mathematicae Graph Theory, Tome 27 (2007) pp. 553-558. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1380/

[000] [1] Y. Alavi, M. Behzad, L.M. Leśniak-Foster and E.A. Nordhaus, Total matchings and total coverings of graphs, J. Graph Theory 1 (1977) 135-140, doi: 10.1002/jgt.3190010209. | Zbl 0376.05045

[001] [2] Y. Alavi, J. Liu, F.J. Wang and F.Z. Zhang, On total covers of graphs, Discrete Math. 100 (1992) 229-233. Special volume to mark the centennial of Julius Petersen's ``Die Theorie der regulären Graphs'', Part I, doi: 10.1016/0012-365X(92)90643-T.

[002] [3] I. Dinur and S. Safra, On the hardness of approximating minimum vertex cover, Annals of Mathematics 162 (2005) 439-485, doi: 10.4007/annals.2005.162.439. | Zbl 1084.68051

[003] [4] R. Duh and M. Fürer, Approximation of k-set cover by semi-local optimization, Proceedings of STOC '97: the 29th Annual ACM Symposium on Theory of Computing, (1997) 256-264. | Zbl 0962.68172

[004] [5] P. Erdös and A. Meir, On total matching numbers and total covering numbers of complementary graphs, Discrete Math. 19 (1977) 229-233, doi: 10.1016/0012-365X(77)90102-9. | Zbl 0374.05047

[005] [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs, vol. 208 of Monographs and Textbooks in Pure and Applied Mathematics (Marcel Dekker Inc., New York, 1998). | Zbl 0890.05002

[006] [7] S.M. Hedetniemi, S.T. Hedetniemi, R. Laskar, A. McRae and A. Majumdar, Domination, independence and irredundance in total graphs: a brief survey, in: Y. Alavi and A. Schwenk, eds, Graph Theory, Combinatorics and Applications: Proceedings of the 7th Quadrennial International Conference on the Theory and Applications of Graphs 2 (1995) 671-683. John Wiley and Sons, Inc. | Zbl 0843.05060

[007] [8] D.S. Johnson, Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences (1974) 256-278, doi: 10.1016/S0022-0000(74)80044-9. | Zbl 0296.65036

[008] [9] S. Khot and O. Regev, Vertex cover might be hard to approximate within 2-ε, in: Proceedings of the 17th IEEE Conference on Computational Complexity (2002) 379-386.

[009] [10] A. Majumdar, Neighborhood hypergraphs, PhD thesis, Clemson University, Department of Mathematical Sciences, 1992.

[010] [11] D.F. Manlove, On the algorithmic complexity of twelve covering and independence parameters of graphs, Discrete Appl. Math. 91 (1999) 155-177, doi: 10.1016/S0166-218X(98)00147-4. | Zbl 0922.05041

[011] [12] A. Meir, On total covering and matching of graphs, J. Combin. Theory (B) 24 (1978) 164-168, doi: 10.1016/0095-8956(78)90017-5. | Zbl 0379.05050

[012] [13] U. Peled and F. Sun, Total matchings and total coverings of threshold graphs, Discrete Appl. Math. 49 (1994) 325-330. Viewpoints on optimization (Grimentz, 1990; Boston, MA, 1991). | Zbl 0799.90116