{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:46:18Z","timestamp":1770972378540,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,22]],"date-time":"2021-11-22T00:00:00Z","timestamp":1637539200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,22]],"date-time":"2021-11-22T00:00:00Z","timestamp":1637539200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001868","name":"National Science Council","doi-asserted-by":"publisher","award":["MOST-106-2221-E-019-014-"],"award-info":[{"award-number":["MOST-106-2221-E-019-014-"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001868","name":"National Science Council","doi-asserted-by":"publisher","award":["MOST-107-2221-E-019-016-"],"award-info":[{"award-number":["MOST-107-2221-E-019-016-"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s10878-021-00767-5","type":"journal-article","created":{"date-parts":[[2021,11,22]],"date-time":"2021-11-22T04:41:12Z","timestamp":1637556072000},"page":"269-286","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A linear-time algorithm for weighted paired-domination on block graphs"],"prefix":"10.1007","volume":"44","author":[{"given":"Ching-Chi","family":"Lin","sequence":"first","affiliation":[]},{"given":"Cheng-Yu","family":"Hsieh","sequence":"additional","affiliation":[]},{"given":"Ta-Yu","family":"Mu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,22]]},"reference":[{"key":"767_CR1","volume-title":"The design and analysis of computer algorithms","author":"AV Aho","year":"1974","unstructured":"Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam"},{"key":"767_CR2","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.dam.2019.08.001","volume":"281","author":"GR Argiroffo","year":"2020","unstructured":"Argiroffo GR, Bianchi SM, Lucarini Y, Wagler AK (2020) Linear-time algorithms for three domination-based separation problems in block graphs. Discrete Appl Math 281:6\u201341","journal-title":"Discrete Appl Math"},{"issue":"1","key":"767_CR3","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/s10878-019-00457-3","volume":"39","author":"S Banerjee","year":"2020","unstructured":"Banerjee S, Henning MA, Pradhan D (2020) Algorithmic results on double Roman domination in graphs. J Comb Optim 39(1):90\u2013114","journal-title":"J Comb Optim"},{"key":"767_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.08.017","volume":"796","author":"S Banerjee","year":"2019","unstructured":"Banerjee S, Keil JM, Pradhan D (2019) Perfect Roman domination in graphs. Theoret Comput Sci 796:1\u201321","journal-title":"Theoret Comput Sci"},{"issue":"1","key":"767_CR5","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0167-6377(89)90034-5","volume":"8","author":"GJ Chang","year":"1989","unstructured":"Chang GJ (1989) Total domination in block graphs. Oper Res Lett 8(1):53\u201357","journal-title":"Oper Res Lett"},{"key":"767_CR6","doi-asserted-by":"crossref","unstructured":"Chang GJ (2013) Algorithmic aspects of domination in graphs. In: Handbook of Combinatorial Optimization, pp 339\u2013405. Springer-Verlag, New York, second edition","DOI":"10.1007\/978-1-4419-7997-1_26"},{"issue":"47\u201349","key":"767_CR7","doi-asserted-by":"publisher","first-page":"5063","DOI":"10.1016\/j.tcs.2009.08.004","volume":"410","author":"L Chen","year":"2009","unstructured":"Chen L, Lu C, Zeng Z (2009) Hardness results and approximation algorithms for (weighted) paired-domination graphs. Theoret Comput Sci 410(47\u201349):5063\u20135071","journal-title":"Theoret Comput Sci"},{"issue":"1","key":"767_CR8","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.ipl.2009.09.014","volume":"110","author":"L Chen","year":"2009","unstructured":"Chen L, Lu C, Zeng Z (2009) A linear-time algorithm for paired-domination problem in strongly chordal graphs. Inform Process Lett 110(1):20\u201323","journal-title":"Inform Process Lett"},{"issue":"4","key":"767_CR9","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/s10878-008-9177-6","volume":"19","author":"L Chen","year":"2010","unstructured":"Chen L, Lu C, Zeng Z (2010) Labelling algorithms for paired-domination problems in block and interval graphs. J Comb Optim 19(4):457\u2013470","journal-title":"J Comb Optim"},{"issue":"2","key":"767_CR10","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1016\/j.dam.2008.02.015","volume":"157","author":"TCE Cheng","year":"2009","unstructured":"Cheng TCE, Kang L, Shan E (2009) A polynomial-time algorithm for the paired-domination problem on permutation graphs. Discrete Appl Math 157(2):262\u2013271","journal-title":"Discrete Appl Math"},{"issue":"7","key":"767_CR11","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1016\/j.disc.2012.11.031","volume":"313","author":"W Goddard","year":"2013","unstructured":"Goddard W, Henning MA (2013) Independent domination in graphs: a survey and recent results. Discrete Math 313(7):839\u2013854","journal-title":"Discrete Math"},{"key":"767_CR12","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F","volume":"32","author":"T Haynes","year":"1998","unstructured":"Haynes T, Slater P (1998) Paired-domination in graphs. Networks 32:199\u2013206","journal-title":"Networks"},{"key":"767_CR13","volume-title":"Domination in graphs: advanced topics","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (1998) Domination in graphs: advanced topics. Marcel Dekker Inc., New York"},{"key":"767_CR14","volume-title":"Fundamentals of domination in graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (1998) Fundamentals of domination in graphs. Marcel Dekker Inc., New York"},{"issue":"1\u20133","key":"767_CR15","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0012-365X(90)90365-O","volume":"86","author":"ST Hedetniemi","year":"1990","unstructured":"Hedetniemi ST, Laskar RC (1990) Bibliography on domination in graphs and some basic definitions of domination parameters. Discrete Math 86(1\u20133):257\u2013277","journal-title":"Discrete Math"},{"key":"767_CR16","unstructured":"Hedetniemi ST, Laskar RC (eds) (1991) Topics on domination. Annals of Discrete Mathematics. North-Holland Publishing Co., Amsterdam"},{"issue":"1","key":"767_CR17","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.disc.2007.12.044","volume":"309","author":"MA Henning","year":"2009","unstructured":"Henning MA (2009) A survey of selected recent results on total domination in graphs. Discrete Math 309(1):32\u201363","journal-title":"Discrete Math"},{"key":"767_CR18","doi-asserted-by":"crossref","unstructured":"Henning MA, Pal S, Pradhan D (2019) The semitotal domination problem in block graphs. Discuss Math Graph Theory, 1\u201318","DOI":"10.7151\/dmgt.2254"},{"key":"767_CR19","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.tcs.2019.10.045","volume":"804","author":"MA Henning","year":"2020","unstructured":"Henning MA, Pradhan D (2020) Algorithmic aspects of upper paired-domination in graphs. Theoret Comput Sci 804:98\u2013114","journal-title":"Theoret Comput Sci"},{"issue":"4","key":"767_CR20","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1007\/s00224-011-9378-8","volume":"50","author":"R-W Hung","year":"2012","unstructured":"Hung R-W (2012) Linear-time algorithm for the paired-domination problem in convex bipartite graphs. Theory Comput Syst 50(4):721\u2013738","journal-title":"Theory Comput Syst"},{"key":"767_CR21","series-title":"Handbook of Combinatorial Optimization","first-page":"3363","volume-title":"Variations of dominating set problem","author":"L Kang","year":"2013","unstructured":"Kang L (2013) Variations of dominating set problem, 2nd edn. Handbook of Combinatorial Optimization. Springer-Verlag, New York, pp 3363\u20133394","edition":"2"},{"issue":"2\u20133","key":"767_CR22","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.tcs.2004.02.028","volume":"320","author":"L Kang","year":"2004","unstructured":"Kang L, Sohn MY, Cheng TCE (2004) Paired-domination in inflated graphs. Theor Comput Sci 320(2\u20133):485\u2013494","journal-title":"Theor Comput Sci"},{"key":"767_CR23","doi-asserted-by":"crossref","unstructured":"Lappas E, Nikolopoulos SD, Palios L (2009) An $$O(n)$$-time algorithm for the paired-domination problem on permutation graphs. In: Combinatorial algorithms, volume 5874 of Lecture Notes in Comput. Sci., pp 368\u2013379. Springer, Berlin","DOI":"10.1007\/978-3-642-10217-2_36"},{"issue":"3","key":"767_CR24","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1016\/j.ejc.2011.10.011","volume":"34","author":"E Lappas","year":"2013","unstructured":"Lappas E, Nikolopoulos SD, Palios L (2013) An $$O(n)$$-time algorithm for the paired domination problem on permutation graphs. European J Combin 34(3):593\u2013608","journal-title":"European J Combin"},{"issue":"10","key":"767_CR25","doi-asserted-by":"publisher","first-page":"2809","DOI":"10.1007\/s00453-020-00705-7","volume":"82","author":"C-C Lin","year":"2020","unstructured":"Lin C-C, Ku K-C, Hsu C-H (2020) Paired-domination problem on distance-hereditary graphs. Algorithmica 82(10):2809\u20132840","journal-title":"Algorithmica"},{"key":"767_CR26","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.tcs.2015.05.002","volume":"591","author":"C-C Lin","year":"2015","unstructured":"Lin C-C, Tu H-L (2015) A linear-time algorithm for paired-domination on circular-arc graphs. Theoret Comput Sci 591:99\u2013105","journal-title":"Theoret Comput Sci"},{"key":"767_CR27","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/j.dam.2018.09.005","volume":"257","author":"C Lu","year":"2019","unstructured":"Lu C, Wang B, Wang K, Wu Y (2019) Paired-domination in claw-free graphs with minimum degree at least three. Discrete Appl Math 257:250\u2013259","journal-title":"Discrete Appl Math"},{"issue":"12","key":"767_CR28","doi-asserted-by":"publisher","first-page":"1776","DOI":"10.1016\/j.dam.2012.04.014","volume":"161","author":"BS Panda","year":"2013","unstructured":"Panda BS, Pradhan D (2013) A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph. Discrete Appl Math 161(12):1776\u20131783","journal-title":"Discrete Appl Math"},{"issue":"4","key":"767_CR29","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1007\/s10878-012-9483-x","volume":"26","author":"BS Panda","year":"2013","unstructured":"Panda BS, Pradhan D (2013) Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs. J Comb Optim 26(4):770\u2013785","journal-title":"J Comb Optim"},{"issue":"2","key":"767_CR30","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s10878-017-0197-y","volume":"35","author":"D Pradhan","year":"2018","unstructured":"Pradhan D, Jha A (2018) On computing a minimum secure dominating set in block graphs. J Comb Optim 35(2):613\u2013631","journal-title":"J Comb Optim"},{"key":"767_CR31","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.dam.2018.08.022","volume":"253","author":"D Pradhan","year":"2019","unstructured":"Pradhan D, Panda BS (2019) Computing a minimum paired-dominating set in strongly orderable graphs. Discrete Appl Math 253:37\u201350","journal-title":"Discrete Appl Math"},{"issue":"1","key":"767_CR32","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1023\/A:1021338214295","volume":"25","author":"H Qiao","year":"2003","unstructured":"Qiao H, Kang L, Cardei M, Du D-Z (2003) Paired-domination of trees. J Global Optim 25(1):43\u201354","journal-title":"J Global Optim"},{"issue":"1\u20133","key":"767_CR33","doi-asserted-by":"publisher","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 (2006) Power domination in block graphs. Theoret Comput Sci 359(1\u20133):299\u2013305","journal-title":"Theoret Comput Sci"},{"issue":"1\u20133","key":"767_CR34","first-page":"245","volume":"87","author":"H-G Yeh","year":"1998","unstructured":"Yeh H-G, Chang GJ (1998) Weighted connected domination and Steiner trees in distance-hereditary graphs. Discrete Appl Math 87(1\u20133):245\u2013253","journal-title":"Discrete Appl Math"},{"issue":"2","key":"767_CR35","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0166-218X(94)00138-4","volume":"66","author":"C-C Yen","year":"1996","unstructured":"Yen C-C, Lee RCT (1996) The weighted perfect domination problem and its variants. Discrete Appl Math 66(2):147\u2013160","journal-title":"Discrete Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00767-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00767-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00767-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T07:28:23Z","timestamp":1659079703000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00767-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,22]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["767"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00767-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,22]]},"assertion":[{"value":"2 June 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}