# An approximation algorithm for the total covering problem

Discussiones Mathematicae Graph Theory (2007)

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

## Access Full Article

top## Abstract

top## How to cite

topPooya Hatami. "An approximation algorithm for the total covering problem." Discussiones Mathematicae Graph Theory 27.3 (2007): 553-558. <http://eudml.org/doc/270525>.

@article{PooyaHatami2007,

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 = {http://eudml.org/doc/270525},

volume = {27},

year = {2007},

}

TY - JOUR

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 - http://eudml.org/doc/270525

ER -

## References

top- [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] 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. Zbl1084.68051
- [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] 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] 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] 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] 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] 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. Zbl0922.05041
- [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] 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 ?

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