An approximation algorithm for the total covering problem

 Access to full text

 Full (PDF)

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