{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T08:48:11Z","timestamp":1764060491279},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,6,8]],"date-time":"2011-06-08T00:00:00Z","timestamp":1307491200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00453-011-9533-2","type":"journal-article","created":{"date-parts":[[2011,6,7]],"date-time":"2011-06-07T19:58:47Z","timestamp":1307476727000},"page":"323-346","source":"Crossref","is-referenced-by-count":12,"title":["An Exact Exponential Time Algorithm for Power Dominating Set"],"prefix":"10.1007","volume":"63","author":[{"given":"Daniel","family":"Binkele-Raible","sequence":"first","affiliation":[]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,6,8]]},"reference":[{"issue":"3","key":"9533_CR1","doi-asserted-by":"crossref","first-page":"1382","DOI":"10.1137\/06066672X","volume":"23","author":"A. Aazami","year":"2009","unstructured":"Aazami, A., Stilp, K.: Approximation algorithms and hardness for domination with propagation. SIAM J. Discrete Math. 23(3), 1382\u20131399 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"9533_CR2","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1137\/S0895480103432556","volume":"19","author":"D.J. Brueni","year":"2006","unstructured":"Brueni, D.J., Heath, L.S.: The PMU placement problem. SIAM J. Discrete Math. 19, 744\u2013761 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"9533_CR3","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/j.ipl.2004.10.003","volume":"93","author":"L.S. Chandran","year":"2005","unstructured":"Chandran, L.S., Grandoni, F.: Refined memorization for vertex cover. Inf. Process. Lett. 93, 125\u2013131 (2005)","journal-title":"Inf. Process. Lett."},{"key":"9533_CR4","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1007\/978-3-540-77891-2_14","volume-title":"Workshop on Algorithms and Computation: WALCOM","author":"H. Fernau","year":"2008","unstructured":"Fernau, H., Raible, D.: Exact algorithms for maximum acyclic subgraph on a superclass of cubic graphs. In: Nakano, S.-I., Rahman, Md.S. (eds.) Workshop on Algorithms and Computation: WALCOM. LNCS, vol. 4921, pp. 144\u2013156. Springer, Berlin (2008)"},{"key":"9533_CR5","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/978-3-642-11269-0_13","volume-title":"International Workshop on Parameterized and Exact Computation (IWPEC)","author":"H. Fernau","year":"2009","unstructured":"Fernau, H., Langer, A., Liedloff, M., Kneis, J., Kratsch, D., Raible, D., Rossmanith, P.: An exact algorithm for the maximum leaf spanning tree problem. In: Chen, J., Fomin, F.V. (eds.) International Workshop on Parameterized and Exact Computation (IWPEC). LNCS, vol. 5917, pp. 161\u2013172. Springer, Berlin (2009)"},{"key":"9533_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms. Texts in Theoretical Computer Science","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. Springer, Berlin (2010)"},{"key":"9533_CR7","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Technical Report 307, Department of Informatics, University of Bergen (2005)"},{"issue":"2","key":"9533_CR8","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/s00453-007-9145-z","volume":"52","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Solving connected dominating set faster than 2 n . Algorithmica 52(2), 153\u2013166 (2008)","journal-title":"Algorithmica"},{"key":"9533_CR9","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J.\u00a0ACM 56(5) (2009)","DOI":"10.1145\/1552285.1552286"},{"issue":"4","key":"9533_CR10","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"9533_CR11","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s00453-007-9147-x","volume":"52","author":"J. Guo","year":"2008","unstructured":"Guo, J., Niedermeier, R., Raible, D.: Improved algorithms and complexity results for power domination in graphs. Algorithmica 52(2), 177\u2013202 (2008)","journal-title":"Algorithmica"},{"issue":"4","key":"9533_CR12","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1137\/S0895480100375831","volume":"15","author":"T.W. Haynes","year":"2002","unstructured":"Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM J. Discrete Math. 15(4), 519\u2013529 (2002)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"9533_CR13","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.ipl.2006.01.007","volume":"98","author":"J. Kneis","year":"2006","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: Parameterized power domination complexity. Inf. Process. Lett. 98(4), 145\u2013149 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9533_CR14","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1007\/11533719_83","volume-title":"Computing and Combinatorics","author":"C.-S. Liao","year":"2005","unstructured":"Liao, C.-S., Lee, D.-T.: Power domination problem in graphs. In: Wang, L. (ed.) Computing and Combinatorics, 11th Annual International Conference, COCOON. LNCS, vol. 3595, pp. 818\u2013828. Springer, Berlin (2005)"},{"issue":"4","key":"9533_CR15","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/j.ijepes.2005.05.005","volume":"28","author":"J. Peng","year":"2006","unstructured":"Peng, J., Sun, Y., Wang, H.F.: Optimal PMU placement for full network observability using tabu search algorithm. Int. J. Electr. Power Energy Syst. 28(4), 223\u2013231 (2006)","journal-title":"Int. J. Electr. Power Energy Syst."},{"key":"9533_CR16","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/978-3-540-92182-0_15","volume-title":"Algorithms and Computation","author":"D. Raible","year":"2008","unstructured":"Raible, D., Fernau, H.: Power domination in O \u2217(1.7548 n ) using reference search trees. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) Algorithms and Computation, 19th International Symposium, ISAAC 2008. LNCS, vol. 5369, pp. 136\u2013147. Springer, Berlin (2008)"},{"key":"9533_CR17","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1007\/978-3-642-11266-9_56","volume-title":"SOFSEM 2010: Theory and Practice of Computer Science","author":"D. Raible","year":"2010","unstructured":"Raible, D., Fernau, H.: An amortized search tree analysis for k-Leaf Spanning Tree. In: van Leeuwen, J., Muscholl, A., Peleg, D., Pokorn\u00fd, J., Rumpe, B. (eds.) SOFSEM 2010: Theory and Practice of Computer Science. LNCS, vol. 5901, pp. 672\u2013684. Springer, Berlin (2010)"},{"issue":"3","key":"9533_CR18","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J.M. Robson","year":"1986","unstructured":"Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7(3), 425\u2013440 (1986)","journal-title":"J. Algorithms"},{"key":"9533_CR19","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1002\/jgt.3190120311","volume":"3","author":"E. Speckenmeyer","year":"1988","unstructured":"Speckenmeyer, E.: On feedback vertex sets and nonseparating independent sets in cubic graphs. J.\u00a0Graph Theory 3, 405\u2013412 (1988)","journal-title":"J.\u00a0Graph Theory"},{"key":"9533_CR20","series-title":"Dagstuhl Seminar Proceedings","first-page":"657","volume-title":"Symposium on Theoretical Aspects of Computer Science (STACS)","author":"J.M.M. Rooij van","year":"2008","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Design by measure and conquer, a faster exact algorithm for dominating set. In: Albers, S., Weil, P. (eds.) Symposium on Theoretical Aspects of Computer Science (STACS), Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany. Dagstuhl Seminar Proceedings, vol. 08001, pp. 657\u2013668 (2008)"},{"key":"9533_CR21","series-title":"LNCS","first-page":"554","volume-title":"European Symposium on Algorithms (ESA)","author":"J.M.M. Rooij van","year":"2009","unstructured":"van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion\/exclusion meets measure and conquer. In: Fiat, A., Sanders, P. (eds.) European Symposium on Algorithms (ESA). LNCS, vol. 5757, pp. 554\u2013565. Springer, Berlin (2009)"},{"key":"9533_CR22","first-page":"67","volume-title":"International Joint Journal Conference on Engineering and Technology (IJJCET10)","author":"G. Venugopal","year":"2010","unstructured":"Venugopal, G., Veilumuthu, R., Avila Theresa, P.: Optimal PMU placement and observability of power system using PSAT. In: International Joint Journal Conference on Engineering and Technology (IJJCET10), pp. 67\u201371 (2010). Available online: http:\/\/ijjcet.com\/content.htm"},{"key":"9533_CR23","unstructured":"Wang, K., Cai, Z., Ding, J.: PMU placement and the state estimation model of a hybrid measurement system"},{"issue":"1\u20133","key":"9533_CR24","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.tcs.2006.04.011","volume":"359","author":"G. Xu","year":"2006","unstructured":"Xu, G., Kang, L., Shan, E., Zhao, M.: Power domination in block graphs. Theor. Comput. Sci. 359(1\u20133), 299\u2013305 (2006)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9533-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9533-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9533-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T13:43:10Z","timestamp":1560260590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9533-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,8]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9533"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9533-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,8]]}}}