PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1995 | 15 | 1 | 51-57
Tytuł artykułu

The edge domination problem

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
An edge dominating set of a graph is a set D of edges such that every edge not in D is adjacent to at least one edge in D. In this paper we present a linear time algorithm for finding a minimum edge dominating set of a block graph.
Słowa kluczowe
Wydawca
Rocznik
Tom
15
Numer
1
Strony
51-57
Opis fizyczny
Daty
wydano
1995
otrzymano
1994-04-27
Twórcy
  • Department of Computer Science, Feng Chia University, Taichung 40724, Taiwan
  • Department of Applied Mathematics, National Chiao Tung University, Hsinchu 30050 Taiwan
Bibliografia
  • [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974).
  • [2] R. D. Dutton and R. C. Brigham, An extremal problem for the edge domination insensitive graphs, Discrete Applied Math. 20 (1988) 113-125, doi: 10.1016/0166-218X(88)90058-3.
  • [3] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).
  • [4] S. R. Jayaram, Line domination in graphs, Graphs and Combin. 3 (1987) 357-363, doi: 10.1007/BF01788558.
  • [5] S. Mitchell and S. T. Hedetniemi, Edge domination in trees, in: Proc. 8th S. E. Conf. Combin., Graph Theory and Computing, Congr. Numer. 19 (1977) 489-509.
  • [6] P. S. Neeralagi, Strong, weak edge domination in a graph, manuscript, November 1988.
  • [7] M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38 (1980) 364-372, doi: 10.1137/0138030.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1006
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ć.