Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-10T13:18:36.335Z Has data issue: false hasContentIssue false
  • English
  • Français

Domination problems on P5-free graphs∗

Published online by Cambridge University Press:  12 January 2015

Min Chih Lin  and
Michel J. Mizrahi
Min Chih Lin
Affiliation:
Intendente Güiraldes 2160, C1428EGA Buenos Aires, Buenos Aires Province, Argentina. oscarlin@dc.uba.ar; michel.mizrahi@gmail.com
Michel J. Mizrahi
Affiliation:
Intendente Güiraldes 2160, C1428EGA Buenos Aires, Buenos Aires Province, Argentina. oscarlin@dc.uba.ar; michel.mizrahi@gmail.com

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The minimum roman dominating problem (denoted by γR(G),the weight of minimum roman dominating function of graph G) is a variant of the verywell known minimum dominating set problem (denoted by γ(G), thecardinality of minimum dominating set of graph G). Both problems remain NP-Complete when restrictedto P5-free graph class [A.A. Bertossi,Inf. Process. Lett. 19 (1984) 37–40; E.J. Cockayne,et al. Discret. Math. 278 (2004) 11–22]. In this paper westudy both problems restricted to some subclasses of P5-free graphs.We describe robust algorithms that solve both problems restricted to (P5,(s,t)-net)-free graphsin polynomial time. This result generalizes previous works for both problems, and improvesexisting algorithms when restricted to certain families such as (P5,bull)-freegraphs. It turns out that the same approach also serves to solve problems for generalgraphs in polynomial time whenever γ(G) and γR(G)are fixed (more efficiently than naive algorithms). Moreover, the algorithms described areextremely simple which makes them useful for practical purposes, and as we show in thelast section it allows to simplify algorithms for significant classes such ascographs.

Keywords

Algorithmsdominating setroman dominating functionP5-free graphs

Information

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 48 , Issue 5 , December 2014 , pp. 541 - 549
Copyright
© EDP Sciences 2015

References

Bacso, G. and Tuza, Zs., Dominating cliques in P 5-free graphs. Period. Math. Hung. 21 (1990) 303–308. Google Scholar
Bertossi, A.A., Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19 (1984) 37–40. Google Scholar
Booth, K.S. and Howard Johnson, J., Dominating sets in chordal graphs. SIAM J. Comput. 11 (1982) 191–199. Google Scholar
Chang, Maw-Shang, Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27 (1998) 1671–1694. Google Scholar
Chao, H.S., Hsu, Fang-Rong and C.T. Lee, Richard, An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs. Discrete Appl. Math. 102 (2000) 159–173. Google Scholar
Chiba, N. and Nishizeki, T., Arboricity and subgraph listing algorithms. SIAM J. Comput. 14 (1985) 210–223. Google Scholar
Cockayne, E.J., Dreyer, P.A. Jr., Hedetniemi, S.M. and Hedetniemi, S.T., Roman domination in graphs. Discrete Math. 278 (2004) 11–22. Google Scholar
Cooper, C., Klasing, R. and Zito, M., Lower bounds and algorithms for dominating sets in web graphs. Internet Math. 2 (2005) 275–300. Google Scholar
Farber, M. and Mark Keil, J., Domination in permutation graphs. J. Algorithms 6 (1985) 309–321. Google Scholar
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Series of Books in Math. Sci. W.H. Freeman (1979).
Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T. and Henning, M.A., Domination in graphs applied to electric power networks. SIAM J. Discrete Math. 15 (2002) 519–529. Google Scholar
T.W. Haynes, P.J. Slater and S.T. Hedetniemi, Fundamentals of domination in graphs. Includes bibliographical references and index (1998) 355–438.
Kratsch, D., Domination and total domination on asteroidal triple-free graphs. Discrete Appl. Math. 99 (2000) 111–123. Google Scholar
Liedloff, M., Kloks, T., Liu, J., Peng, S.-L., Efficient algorithms for roman domination on some classes of graphs. Discrete Appl. Math. 156 (2008) 3400–3415. Google Scholar
Müller, H. and Brandstädt, A., The np-completeness of steiner tree and dominating set for chordal bipartite graphs. Theoret. Comput. Sci. 53 (1987) 257–265. Google Scholar
Nicolai, F. and Szymczak, T., Homogeneous sets and domination: A linear time algorithm for distance – hereditary graphs. Networks 37 (2001) 117–128. Google Scholar
J. Wu and H. Li, Domination and its applications in ad hoc wireless networks with unidirectional links. In Proc. of International Conference on Parallel Processing (2000).
Zverovich, I. E.. The domination number of (Kp, P5)-free graphs. Australas. J. Combin. 27 (2003) 95–100. Google Scholar