PDF
Discussiones Mathematicae Graph Theory 27(3) (2007)
553-558
DOI: https://doi.org/10.7151/dmgt.1380
AN APPROXIMATION ALGORITHM FOR THE TOTAL COVERING PROBLEM
Pooya Hatami
Department of Mathematical Sciences
Sharif University of Technology
Tehran, Iran
e-mail: p_hatami@ce.sharif.edu
Abstract
We introduce a 2-factor approximation algorithm for the minimum total covering number problem.Keywords: covering, total covering, approximation algorithm.
2000 Mathematics Subject Classification: 05C69.
References
[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. |
[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. |
[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. |
[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. |
[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. |
[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). |
[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. |
[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. |
[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. |
[10] | A. Majumdar, Neighborhood hypergraphs, PhD thesis, Clemson University, Department of Mathematical Sciences, 1992. |
[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. |
[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. |
[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). |
Received 20 September 2006
Revised 30 December 2006
Accepted 3 January 2007
Close