An efficient algorithm for Mixed domination on Generalized Series-Parallel Graphs

Document Type : Research Paper

Authors

1 Department of Computer Science, Yazd University, Yazd, Iran.

2 Department of Computer Science, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran.

3 Department of Computer Science, The University of Auckland, Auckland, New Zealand.

Abstract

A mixed dominating set $S$ of a graph $G=(V, E)$ is a subset of vertices and edges like $S \subseteq V \cup E$ such that each element $v\in (V \cup E) \setminus S$ is adjacent or incident to at least one element in $S$. The mixed domination number $\gamma_m(G)$ of a graph $G$ is the minimum cardinality among all mixed dominating sets in $G$. The problem of finding  $\gamma_{m}(G)$ is known to be  NP-complete. In this paper, we present an explicit polynomial-time algorithm using the parse tree to construct a mixed dominating set of size $\gamma_{m}(G)$  where $G$ is a generalized series-parallel graph.

Keywords

References

[1] G. S. Adhar, S. Peng, Mixed domination in trees: a parallel algorithm, Congr. Numer. 100 (1994) 73-80.
[2] Y. Alavi, M. Behzad, L. M. Lesniak-Foster, E. Nordhaus, Total matchings and total coverings of graphs, J. Graph Theory 1(2) (1977) 135-140.
[3] Y. Alavi, J. Liu, J. Wang, Z. Zhang, On total covers of graphs, Discrete Math. 100 (1992) 229-233.
[4] P. Chebolu, M. Cryan, R. Martin, Exact counting of Euler tours for generalized series-parallel graphs, J. Discrete Algorithms 10 (2012) 110-122.
[5] T. W. Haynes, S. Hedetniemi, P. Slater, Fundamentals of domination in graphs, CRC Press, 1998.
[6] T. W. Haynes, S. Hedetniemi, P. Slater, Domination in graphs: advanced topics, Taylor & Francis, 1998.
[7] S. M. Hedetniemi, S. T. Hedetniemi, R. Laskar, A. McRae, A. Majumdar, Domination, independence and irredundance in total graphs: a brief survey, Graph Theory, Combinatorics and Applications: Proceedings of the 7th Quadrennial International Conference on the Theory and Applications of Graphs 2 (1995) 671-683.
[8] J. E. Hopcroft, R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2(3) (1973) 135-158.
[9] T. Kikuno, N. Yoshida,Y. Kakuda, A linear algorithm for the domination number of a series-parallel graph, Discrete Appl. Math. 5(3) (1983) 299-311.
[10] J. K. Lan, G. J. Chang, On the mixed domination problem in graphs, Theoret. Comput. Sci. 476(84) (2013) 84-93.
[11] A. Majumdar, Neighborhood Hypergraphs: A Framework for Covering and Packing Parameters in Graphs, PhD thesis,
Clemson University, Department of Mathematical Sciences, South Carolina, 1992.
[12] D. F. Manlove, On the algorithmic complexity of twelve covering and independence parameters of graphs, Discrete Appl. Math. 91(1) (1999) 155-175.
[13] M. Rajaati, M. R. Hooshmandasl, M. J. Dinneen, A. Shakiba, On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width, Discrete Math. Theor. Comput. Sci. 20(2) (2018) 1-25.
[14] D. B. West, Introduction to graph theory, Prentice Hall Upper Saddle River, 2001.
[15] Y. Zhao, L. Kang, M. Y. Sohn, The algorithmic complexity of mixed domination in graphs, Theoret. Comput. Sci.
412(22) (2011) 2387-2392.
Algebraic Structures and Their Applications
Volume 5, Issue 1
February 2018
Pages 23-39

Files

Share

How to cite

Statistics