PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2007 | 27 | 3 | 553-558
Tytuł artykułu

An approximation algorithm for the total covering problem

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We introduce a 2-factor approximation algorithm for the minimum total covering number problem.
Słowa kluczowe
Wydawca
Rocznik
Tom
27
Numer
3
Strony
553-558
Opis fizyczny
Daty
wydano
2007
otrzymano
2006-09-20
poprawiono
2006-12-30
zaakceptowano
2007-01-03
Twórcy
autor
  • Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran
Bibliografia
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1380
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.