[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Power Domination in \(\mathcal{O}^*(1.7548^n)\) Using Reference Search Trees

  • Conference paper
Algorithms and Computation (ISAAC 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5369))

Included in the following conference series:

  • 1612 Accesses

Abstract

The Power Dominating Set problem is an extension of the well-known domination problem on graphs in a way that we enrich it by a second propagation rule: Given a graph G(V,E) a set P ⊆ V is a power dominating set if every vertex is observed after we have applied the next two rules exhaustively. First, a vertex is observed if v ∈ P or it has a neighbor in P. Secondly, if an observed vertex has exactly one unobserved neighbor u, then also u will be observed as well. We show that Power Dominating Set remains \(\mathcal{NP}\)-hard on cubic graphs. We designed an algorithm solving this problem in time \(\mathcal{O}^*(1.7548^n)\) on general graphs. To achieve this we have used a new notion of search trees called reference search trees providing non-local pointers.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aazami, A., Stilp, M.D.: Approximation algorithms and hardness for domination with propagation. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol. 4627, pp. 1–15. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  2. Fernau, H., Raible, D.: Exact algorithms for maximum acyclic subgraph on a superclass of cubic graphs. In: Nakano, S.-i., Rahman, M. S. (eds.) WALCOM 2008. LNCS, vol. 4921, pp. 144–156. Springer, Heidelberg (2008); long version available as Technical Report 08-5, Technical Reports Mathematics / Computer Science, University of Trier, Germany (2008)

    Chapter  Google Scholar 

  3. Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: domination – a case study. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 191–203. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  4. Fomin, F.V., Grandoni, F., Kratsch, D.: Solving connected dominating set faster than 2n. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol. 4337, pp. 152–163. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  5. Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826–834 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  6. Guo, J., Niedermeier, R., Raible, D.: Improved algorithms and complexity results for power domination in graphs. In: Liśkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 172–184. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  7. Haynes, T.W., Mitchell Hedetniemi, S., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM J. Discrete Math. 15(4), 519–529 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  8. Kneis, J., Mölle, D., Richter, S., Rossmanith, P.: Parameterized power domination complexity. Inf. Process. Lett. 98(4), 145–149 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Liao, C.-S., Lee, D.-T.: Power domination problem in graphs. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 818–828. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  10. Speckennmeyer, E.: On feedback vertex sets and nonseparating independent sets in cubic graphs. Journal of Graph Theory 3, 405–412 (1988)

    Article  MathSciNet  Google Scholar 

  11. van Rooij, J.M.M., Bodlaender, H.L.: Design by measure and conquer, a faster exact algorithm for dominating set. In: STACS 2008, volume 08001 of Dagstuhl Seminar Proceedings. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, pp. 657–668 (2008)

    Google Scholar 

  12. Xu, G., Kang, L., Shan, E., Zhao, M.: Power domination in block graphs. Theor. Comput. Sci. 359(1-3), 299–305 (2006)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Univ. Trier, FB 4—Abteilung Informatik, 54286, Trier, Germany

    Daniel Raible & Henning Fernau

Authors
  1. Daniel Raible
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Henning Fernau
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Information Technologies, University of Sydney, Australia

    Seok-Hee Hong

  2. Graduate School of Informatics, Kyoto University, 606-8501, Kyoto, Japan

    Hiroshi Nagamochi

  3. Graduate School of Informatics, Kyoto University, Japan

    Takuro Fukunaga

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Raible, D., Fernau, H. (2008). Power Domination in \(\mathcal{O}^*(1.7548^n)\) Using Reference Search Trees. In: Hong, SH., Nagamochi, H., Fukunaga, T. (eds) Algorithms and Computation. ISAAC 2008. Lecture Notes in Computer Science, vol 5369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92182-0_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-92182-0_15

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-92181-3

  • Online ISBN: 978-3-540-92182-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics