Algorithmic aspects of majority domination

Hong Gwa Yeh, Gerard J. Chang

研究成果: 雜誌貢獻期刊論文同行評審

12 引文 斯高帕斯(Scopus)


This paper studies algorithmic aspects of majority domination, which is a variation of domination in graph theory. A majority dominating function of a graph G = (V, E) is a function g from V to {-1, 1} such that Σu∈N[v] g(u) ≥ 1 for at least half of the vertices v ∈ V. The majority domination problem is to find a majority dominating function g of a given graph G = (V, E) such that Σv∈V g(v) is minimized. The concept of majority domination was introduced by Hedetniemi and studied by Broere et al., who gave exact values for the majority domination numbers of complete graphs, complete bipartite graphs, paths, and unions of two complete graphs. They also proved that the majority domination problem is NP-complete for general graphs; and asked if the problem NP-complete for trees. The main result of this paper is to give polynomial-time algorithms for the majority domination problem in trees, cographs, and k-trees with fixed k.

頁(從 - 到)343-350
期刊Taiwanese Journal of Mathematics
出版狀態已出版 - 9月 1997


深入研究「Algorithmic aspects of majority domination」主題。共同形成了獨特的指紋。