The edge domination problem

• Autorzy: Shiow-Fen Hwang , Gerard J. Chang
• 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

EN

edge domination; block graph; depth first search

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1995
• Tom: 15
• Numer: 1
• Strony: 51-57

Daty

wydano

1995

otrzymano

1994-04-27

Twórcy

autor

Shiow-Fen Hwang

• Department of Computer Science, Feng Chia University, Taichung 40724, Taiwan

autor

Gerard J. Chang

• 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.

Identyfikatory

DOI

10.7151/dmgt.1006