Algorithms for Minimum Membership Dominating Set problem

Open Access

Issue		RAIRO-Oper. Res. Volume 59, Number 5, September-October 2025


Page(s)		3267 - 3284
DOI		https://doi.org/10.1051/ro/2025125
Published online		31 October 2025

F.N. Abu-Khzam, An improved exact algorithm for minimum dominating set in chordal graphs. Inf. Process. Lett. 174 (2022) 106206. [Google Scholar]
A. Agrawal, P. Choudhary, N.S. Narayanaswamy, K.K. Nisha and V. Ramamoorthi, Parameterized complexity of minimum membership dominating set. Algorithmica 85 (2023) 3430–3452. [Google Scholar]
M. Alambardar Meybodi, F.V. Fomin, A.E. Mouawad and F. Panolan, On the parameterized complexity of [1, j]-domination problems. Theor. Comput. Sci. 804 (2020) 207–218. [Google Scholar]
J. Alber and R. Niedermeier, Improved tree decomposition based algorithms for domination-like problems, in Proceedings of the 5th Latin American Symposium on Theoretical Informatics, LATIN ’02. Springer-Verlag, Berlin, Heidelberg (2002) 613–628. [Google Scholar]
A.A. Bertossi, Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19 (1984) 37–40. [CrossRef] [Google Scholar]
M. Chellali, T.W. Haynes, S.T. Hedetniemi and A. McRae, [1, 2]-sets in graphs. Discrete Appl. Math. 161 (2013) 2885–2893. [Google Scholar]
M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized Algorithms. Springer, Switzerland (2015). [Google Scholar]
F.V. Fomin and D. Kratsch, Exact Exponential Algorithms. Springer (2010). [Google Scholar]
F.V. Fomin, F. Grandoni and D. Kratsch, A measure & conquer approach for the analysis of exact algorithms. J. ACM (JACM) 56 (2009) 1–32. [Google Scholar]
F.V. Fomin, D. Kratsch and G.J. Woeginger, Exact (exponential) algorithms for the dominating set problem, in Graph-Theoretic Concepts in Computer Science, edited by J. Hromkovič, M. Nagl and B. Westfechtel. Springer Berlin Heidelberg, Berlin, Heidelberg (2005) 245–256. [Google Scholar]
R. Ganian, Improving vertex cover as a graph parameter. Discrete Math. Theor. Comput. Sci. 17 (2015) 77–100. [Google Scholar]
A.K. Goharshady, M.R. Hooshmandasl and M.A. Meybodi, [1, 2]-sets and [1, 2]-total sets in trees with algorithms. Discrete Appl. Math. 198 (2016) 136–146. [Google Scholar]
Y. Iwata, A faster algorithm for dominating set analyzed by the potential method, in Parameterized and Exact Computation, edited by D. Marx and P. Rossmanith. Springer Berlin Heidelberg, Berlin, Heidelberg (2012) 41–54. [Google Scholar]
R.M. Karp, Reducibility among Combinatorial Problems. Springer US, Boston, MA (1972). [Google Scholar]
D. Karthika, R. Muthucumaraswamy, M. Bentert, S. Bhyravarapu, S. Saurabh and S. Seetharaman, On the complexity of minimum membership dominating set, in International Conference on Current Trends in Theory and Practice of Computer Science. Springer (2025) 94–107. [Google Scholar]
T. Kikuno, N. Yoshida and Y. Kakuda, The np-completeness of the dominating set problem in cubic planer graphs. IEICE Trans. (1976–1990) 63 (1980) 443–444. [Google Scholar]
F. Kuhn, P. von Rickenbach, R. Wattenhofer, E. Welzl and A. Zollinger, Interference in cellular networks: the minimum membership set cover problem, in Computing and Combinatorics, edited by L. Wang. Springer Berlin Heidelberg, Berlin, Heidelberg (2005) 188–198. [Google Scholar]
M. Liedloff, Finding a dominating set on bipartite graphs. Inf. Process. Lett. 107 (2008) 154–157. [Google Scholar]
N.S. Narayanaswamy, S.M. Dhannya and C. Ramya, Minimum membership hitting sets of axis parallel segments, in Computing and Combinatorics, edited by L. Wang and D. Zhu. Springer International Publishing, Cham (2018) 638–649. [Google Scholar]
S. Porschen, T. Schmidt, E. Speckenmeyer and A. Wotzlaw, XSAT and NAE-SAT of linear CNF classes. Discrete Appl. Math. 167 (2014) 1–14. [Google Scholar]
T.J. Schaefer, The complexity of satisfiability problems, in Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78. Association for Computing Machinery, New York, NY, USA (1978) 216–226. [Google Scholar]
J.M.M. van Rooij and H.L. Bodlaender, Exact algorithms for dominating set. Discrete Appl. Math. 159 (2011) 2147–2164. [Google Scholar]
J.M.M. van Rooij, H.L. Bodlaender and P. Rossmanith, Dynamic programming on tree decompositions using generalised fast subset convolution, in Algorithms – ESA 2009, edited by A. Fiat and P. Sanders. Springer Berlin Heidelberg, Berlin, Heidelberg (2009) 566–577. [Google Scholar]
D.B. West, Introduction to Graph Theory, 2 edition. Pearson, Chennai (2015). [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.