An approximation algorithm for the total covering problem

Pooya Hatami

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 3, page 553-558
  • ISSN: 2083-5892


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

How to cite


Pooya Hatami. "An approximation algorithm for the total covering problem." Discussiones Mathematicae Graph Theory 27.3 (2007): 553-558. <>.

abstract = {We introduce a 2-factor approximation algorithm for the minimum total covering number problem.},
author = {Pooya Hatami},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {covering; total covering; approximation algorithm},
language = {eng},
number = {3},
pages = {553-558},
title = {An approximation algorithm for the total covering problem},
url = {},
volume = {27},
year = {2007},

AU - Pooya Hatami
TI - An approximation algorithm for the total covering problem
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 3
SP - 553
EP - 558
AB - We introduce a 2-factor approximation algorithm for the minimum total covering number problem.
LA - eng
KW - covering; total covering; approximation algorithm
UR -
ER -


  1. [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. Zbl0376.05045
  2. [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. [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. Zbl1084.68051
  4. [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. Zbl0962.68172
  5. [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. Zbl0374.05047
  6. [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). Zbl0890.05002
  7. [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. Zbl0843.05060
  8. [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. Zbl0296.65036
  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. [10] A. Majumdar, Neighborhood hypergraphs, PhD thesis, Clemson University, Department of Mathematical Sciences, 1992. 
  11. [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. Zbl0922.05041
  12. [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. Zbl0379.05050
  13. [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). Zbl0799.90116

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.