PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2002 | 22 | 2 | 229-231
Tytuł artykułu

A note on domination in bipartite graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.
Słowa kluczowe
Kategorie tematyczne
Wydawca
Rocznik
Tom
22
Numer
2
Strony
229-231
Opis fizyczny
Daty
wydano
2002
otrzymano
2000-08-24
Twórcy
  • Department of Mathematics, Technical University of Ilmenau, D-98684 Ilmenau, Germany
  • Department of Mathematics, Technical University of Ilmenau, D-98684 Ilmenau, Germany
Bibliografia
  • [1] G.J. Chang and G.L. Nemhauser, The k-domination and k-stability problems in sun-free chordal graphs, SIAM J. Algebraic Discrete Methods 5 (1984) 332-345, doi: 10.1137/0605034.
  • [2] R. Diestel, Graph Theory (Springer-Verlag, New York, 2000).
  • [3] M.R. Garey and D.S. Johnson, Computers and Intractability (W.H. Freeman and Company, San Francisco, 1979).
  • [4] J. Harant, A. Pruchnewski and M. Voigt, On dominating sets and independent sets of graphs, Combinatorics, Probability and Computing 8 (1999) 547-553, doi: 10.1017/S0963548399004034.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1171
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ć.