The edge domination problem
Shiow-Fen Hwang; Gerard J. Chang
Discussiones Mathematicae Graph Theory (1995)
- Volume: 15, Issue: 1, page 51-57
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topShiow-Fen Hwang, and Gerard J. Chang. "The edge domination problem." Discussiones Mathematicae Graph Theory 15.1 (1995): 51-57. <http://eudml.org/doc/270268>.
@article{Shiow1995,
abstract = {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.},
author = {Shiow-Fen Hwang, Gerard J. Chang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge domination; block graph; depth first search; mixed edge dominating set; linear time algorithm},
language = {eng},
number = {1},
pages = {51-57},
title = {The edge domination problem},
url = {http://eudml.org/doc/270268},
volume = {15},
year = {1995},
}
TY - JOUR
AU - Shiow-Fen Hwang
AU - Gerard J. Chang
TI - The edge domination problem
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 1
SP - 51
EP - 57
AB - 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.
LA - eng
KW - edge domination; block graph; depth first search; mixed edge dominating set; linear time algorithm
UR - http://eudml.org/doc/270268
ER -
References
top- [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974). Zbl0326.68005
- [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. Zbl0638.05031
- [3] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979). Zbl0411.68039
- [4] S. R. Jayaram, Line domination in graphs, Graphs and Combin. 3 (1987) 357-363, doi: 10.1007/BF01788558. Zbl0628.05056
- [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. Zbl0433.05023
- [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. Zbl0455.05047
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.