{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T05:40:52Z","timestamp":1771306852113,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,12,7]],"date-time":"2007-12-07T00:00:00Z","timestamp":1196985600000},"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":[[2008,10]]},"DOI":"10.1007\/s00453-007-9147-x","type":"journal-article","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T17:57:43Z","timestamp":1196963863000},"page":"177-202","source":"Crossref","is-referenced-by-count":55,"title":["Improved Algorithms and Complexity Results for Power Domination in Graphs"],"prefix":"10.1007","volume":"52","author":[{"given":"Jiong","family":"Guo","sequence":"first","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Raible","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,12,7]]},"reference":[{"key":"9147_CR1","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Proc. 10th APPROX\/11th RANDOM","author":"A. Aazami","year":"2007","unstructured":"Aazami, A., Stilp, M.D.: Approximation algorithms and hardness for domination with propagation. In: Proc. 10th APPROX\/11th RANDOM. Lecture Notes in Computer Science, vol.\u00a04627, pp.\u00a01\u201315. Springer, Berlin (2007)"},{"issue":"1\u20132","key":"9147_CR2","first-page":"27","volume":"1","author":"C. Adjih","year":"2005","unstructured":"Adjih, C., Jacquet, P., Viennot, L.: Computing connected dominating sets with multipoint relays. Ad\u00a0Hoc Sens. Wirel. Netw. 1(1\u20132), 27\u201339 (2005)","journal-title":"Ad\u00a0Hoc Sens. Wirel. Netw."},{"issue":"4","key":"9147_CR3","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for Dominating Set and related problems on planar graphs. Algorithmica 33(4), 461\u2013493 (2002)","journal-title":"Algorithmica"},{"issue":"4","key":"9147_CR4","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.jcss.2004.03.007","volume":"71","author":"J. Alber","year":"2005","unstructured":"Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F., Stege, U.: A refined search tree technique for Dominating Set on planar graphs. J. Comput. Syst. Sci. 71(4), 385\u2013405 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9147_CR5","first-page":"363","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial time data reduction for Dominating Set. J.\u00a0ACM 51(3), 363\u2013384 (2004)","journal-title":"J.\u00a0ACM"},{"key":"9147_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/3-540-45995-2_52","volume-title":"Proc. 5th LATIN","author":"J. Alber","year":"2002","unstructured":"Alber, J., Niedermeier, R.: Improved tree decomposition based algorithms for domination-like problems. In: Proc. 5th LATIN. Lecture Notes in Computer Science, vol. 2286, pp. 613\u2013628. Springer, Berlin (2002)"},{"key":"9147_CR7","volume-title":"Complexity and Approximation\u2014Combinatorial Optimization Problems and Their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation\u2014Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (1999)"},{"key":"9147_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"9147_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/11847250","volume-title":"Proc. 32nd WG","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L.: Treewidth: Characterizations, applications, and computations. In: Proc. 32nd WG. Lecture Notes in Computer Science, vol. 4271, pp. 1\u201314. Springer, Berlin (2006)"},{"key":"9147_CR10","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1137\/0211015","volume":"11","author":"K.S. Booth","year":"1982","unstructured":"Booth, K.S., Johnson, J.H.: Dominating sets in chordal graphs. SIAM J. Comput. 11, 191\u2013199 (1982)","journal-title":"SIAM J. Comput."},{"key":"9147_CR11","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: a Survey. SIAM Monographs on Discrete Mathematics and Applications (1999)","DOI":"10.1137\/1.9780898719796"},{"issue":"3","key":"9147_CR12","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1137\/S0895480103432556","volume":"19","author":"D.J. Brueni","year":"2005","unstructured":"Brueni, D.J., Heath, L.S.: The PMU placement problem. SIAM J. Discrete Math. 19(3), 744\u2013761 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"9147_CR13","first-page":"590","volume-title":"Proc. 16th SODA","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality: New connections between FPT algorithms and PTASs. In: Proc. 16th SODA, pp. 590\u2013601. ACM\/SIAM, New York (2005)"},{"key":"9147_CR14","unstructured":"Dewdney, A.K.: Fast Turing reductions between problems in NP: chap. 4; reductions between NP-complete problems. Technical report, Department of Computer Science, University of Western Ontario, Canada, 1981"},{"issue":"6","key":"9147_CR15","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1016\/j.dam.2005.08.006","volume":"154","author":"M. Dorfling","year":"2006","unstructured":"Dorfling, M., Henning, M.A.: A note on power domination in grid graphs. Discrete Appl. Math. 154(6), 1023\u20131027 (2006)","journal-title":"Discrete Appl. Math."},{"key":"9147_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"issue":"4","key":"9147_CR17","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln\u2009n for approximating Set Cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"9147_CR18","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9147_CR19","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9147_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/978-3-540-28639-4_15","volume-title":"Proc. 1st IWPEC","author":"J. Guo","year":"2004","unstructured":"Guo, J., H\u00fcffner, F., Niedermeier, R.: A structural view on parameterizing problems: distance from triviality. In: Proc. 1st IWPEC. Lecture Notes in Computer Science, vol. 3162, pp. 162\u2013173. Springer, Berlin (2004)"},{"issue":"4","key":"9147_CR21","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."},{"key":"9147_CR22","series-title":"Pure and Applied Mathematics","volume-title":"Domination in Graphs: Advanced Topics","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: Advanced Topics. Pure and Applied Mathematics, vol. 209. Dekker, New York (1998)"},{"key":"9147_CR23","volume-title":"Fundamentals of Domination in Graphs, Pure and Applied Mathematics, vol. 208","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs, Pure and Applied Mathematics, vol. 208. Dekker, New York (1998)"},{"key":"9147_CR24","first-page":"889","volume-title":"Handbook of Graph Theory","author":"T.W. Haynes","year":"2004","unstructured":"Haynes, T.W., Henning, M.A.: Domination in graphs. In: Gross, J.L., Yellen, J. (eds.) Handbook of Graph Theory, pp. 889\u2013909. CRC Press, Boca Raton (2004)"},{"key":"9147_CR25","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(92)90201-K","volume":"36","author":"J.M. Keil","year":"1992","unstructured":"Keil, J.M.: The complexity of domination problems in circle graphs. Discrete Appl. Math. 36, 25\u201334 (1992)","journal-title":"Discrete Appl. Math."},{"key":"9147_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994)"},{"issue":"4","key":"9147_CR27","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":"9147_CR28","first-page":"191","volume-title":"Domination in Graphs: Advanced Topics","author":"D. Kratsch","year":"1998","unstructured":"Kratsch, D.: Algorithms. In: Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (eds.) Domination in Graphs: Advanced Topics, pp. 191\u2013231. Dekker, New York (1998)"},{"key":"9147_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1007\/11533719_83","volume-title":"Proc. 11th COCOON","author":"C.S. Liao","year":"2005","unstructured":"Liao, C.S., Lee, D.T.: Power dominating problem in graphs. In: Proc. 11th COCOON. Lecture Notes in Computer Science, vol. 3595, pp. 818\u2013828. Springer, Berlin (2005)"},{"key":"9147_CR30","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)"},{"key":"9147_CR31","unstructured":"Raible, D.: Algorithms and complexity results for power domination in networks. Master\u2019s thesis, Wilhelm-Schickard-Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, Germany (2005). (In German)"},{"key":"9147_CR32","first-page":"85","volume-title":"Recent Advances in Algorithms and Combinatorics","author":"B.A. Reed","year":"2003","unstructured":"Reed, B.A.: Algorithmic aspects of tree width. In: Reed, B.A., Sales, C.L. (eds.) Recent Advances in Algorithms and Combinatorics, pp. 85\u2013107. Springer, Berlin (2003)"},{"key":"9147_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/3-540-57155-8_284","volume-title":"Proc. 3rd WADS","author":"J.A. Telle","year":"1993","unstructured":"Telle, J.A., Proskurowski, A.: Practical algorithms on partial k-trees with an application to domination-like problems. In: Proc. 3rd WADS. Lecture Notes in Computer Science, vol. 709, pp. 610\u2013621. Springer, Berlin (1993)"},{"issue":"4","key":"9147_CR34","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"J.A. Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math. 10(4), 529\u2013550 (1997)","journal-title":"SIAM J. Discrete Math."},{"key":"9147_CR35","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9147-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9147-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9147-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:01Z","timestamp":1559137501000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9147-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,7]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["9147"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9147-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,7]]}}}