TY - GEN
T1 - Algorithmic aspect of minus domination on small-degree graphs
AU - Lin, Jin Yong
AU - Liu, Ching Hao
AU - Poon, Sheung Hung
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - Let G = (V,E) be an undirected graph. A minus dominating function for G is a function f : V → {-1, 0, +1} such that for each vertex v ∈ V , the sum of the function values over the closed neighborhood of v is positive. The weight of a minus dominating function f for G, denoted by w(f(V)), is ∑f(v) over all vertices v ∈ V. The minus domination (MD) number of G is the minimum weight for any minus dominating function for G. The minus domination (MD) problem asks for the minus dominating function which contributes the MD number. In this paper, we first show that the MD problem is W[2]-hard for general graphs. Then we show that the MD problem is NP-complete for subcubic bipartite planar graphs. We further show that the MD problem is APX-hard for graphs of maximum degree seven. Lastly, we present the first fixed-parameter algorithm for the MD problem on subcubic graphs, which runs in O∗ (2.37615k) time, where k is the MD number of the graph.
AB - Let G = (V,E) be an undirected graph. A minus dominating function for G is a function f : V → {-1, 0, +1} such that for each vertex v ∈ V , the sum of the function values over the closed neighborhood of v is positive. The weight of a minus dominating function f for G, denoted by w(f(V)), is ∑f(v) over all vertices v ∈ V. The minus domination (MD) number of G is the minimum weight for any minus dominating function for G. The minus domination (MD) problem asks for the minus dominating function which contributes the MD number. In this paper, we first show that the MD problem is W[2]-hard for general graphs. Then we show that the MD problem is NP-complete for subcubic bipartite planar graphs. We further show that the MD problem is APX-hard for graphs of maximum degree seven. Lastly, we present the first fixed-parameter algorithm for the MD problem on subcubic graphs, which runs in O∗ (2.37615k) time, where k is the MD number of the graph.
UR - http://www.scopus.com/inward/record.url?scp=84951056725&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-21398-9_27
DO - 10.1007/978-3-319-21398-9_27
M3 - Conference contribution
AN - SCOPUS:84951056725
SN - 9783319213972
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 337
EP - 348
BT - Computing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings
A2 - Xu, Dachuan
A2 - Du, Donglei
A2 - Du, Dingzhu
PB - Springer Verlag
T2 - 21st International Conference on Computing and Combinatorics Conference, COCOON 2015
Y2 - 4 August 2015 through 6 August 2015
ER -