{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T06:01:14Z","timestamp":1744783274106,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031221040"},{"type":"electronic","value":"9783031221057"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-22105-7_32","type":"book-chapter","created":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T02:36:12Z","timestamp":1672540572000},"page":"357-367","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Linear-Time Algorithm for\u00a0Paired-Domination on\u00a0Distance-Hereditary Graphs"],"prefix":"10.1007","author":[{"given":"Ta-Yu","family":"Mu","sequence":"first","affiliation":[]},{"given":"Ching-Chi","family":"Lin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,1,1]]},"reference":[{"issue":"8","key":"32_CR1","doi-asserted-by":"publisher","first-page":"1424","DOI":"10.1016\/j.disc.2015.03.014","volume":"338","author":"JD Alvarado","year":"2015","unstructured":"Alvarado, J.D., Dantas, S., Rautenbach, D.: Perfectly relating the domination, total domination, and paired domination numbers of a graph. Discrete Math. 338(8), 1424\u20131431 (2015)","journal-title":"Discrete Math."},{"issue":"3","key":"32_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2019.111724","volume":"343","author":"B Bjorkman","year":"2020","unstructured":"Bjorkman, B.: Infectious power domination of hypergraphs. Discrete Math. 343(3), 111724 (2020)","journal-title":"Discrete Math."},{"issue":"2\u20133","key":"32_CR3","first-page":"135","volume":"80","author":"MS Chang","year":"1997","unstructured":"Chang, M.S.: Weighted domination of cocomparability graphs. Discrete Appl. Math. 80(2\u20133), 135\u2013148 (1997)","journal-title":"Discrete Appl. Math."},{"key":"32_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/3-540-63890-3_37","volume-title":"Algorithms and Computation","author":"M-S Chang","year":"1997","unstructured":"Chang, M.-S., Hsieh, S., Chen, G.-H.: Dynamic programming on distance-hereditary graphs. In: Leong, H.W., Imai, H., Jain, S. (eds.) ISAAC 1997. LNCS, vol. 1350, pp. 344\u2013353. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63890-3_37"},{"issue":"1\u20132","key":"32_CR5","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0166-218X(00)00330-9","volume":"116","author":"MS Chang","year":"2002","unstructured":"Chang, M.S., Wu, S.C., Chang, G.J., Yeh, H.G.: Domination in distance-hereditary graphs. Discrete Appl. Math. 116(1\u20132), 103\u2013113 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"47\u201349","key":"32_CR6","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.: Hardness results and approximation algorithms for (weighted) paired-domination graphs. Theoret. Comput. Sci. 410(47\u201349), 5063\u20135071 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"32_CR7","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.: A linear-time algorithm for paired-domination problem in strongly chordal graphs. Inform. Process. Lett. 110(1), 20\u201323 (2009)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"32_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1006\/jagm.2001.1206","volume":"42","author":"M Damian-Iordache","year":"2002","unstructured":"Damian-Iordache, M., Pemmaraju, S.V.: A $$(2+\\epsilon )$$-approximation scheme for minimum domination on circle graphs. J. Algorithms 42(2), 255\u2013276 (2002)","journal-title":"J. Algorithms"},{"issue":"5","key":"32_CR9","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0020-0190(93)90084-M","volume":"48","author":"DL Grinstead","year":"1993","unstructured":"Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D.: Efficient edge domination problems in graphs. Inform. Process. Lett. 48(5), 221\u2013228 (1993)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"32_CR10","doi-asserted-by":"publisher","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":"32_CR11","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1137\/S0895480100375831","volume":"15","author":"TW 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":"32_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.: Paired-domination in graphs. Networks 32, 199\u2013206 (1998)","journal-title":"Networks"},{"issue":"4","key":"32_CR13","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1137\/S0895480101389880","volume":"15","author":"SY Hsieh","year":"2002","unstructured":"Hsieh, S.Y., Ho, C.W., Hsu, T.S., Ko, M.T., Chen, G.H.: Characterization of efficiently parallel solvable problems on distance-hereditary graphs. SIAM J. Discrete Math. 15(4), 488\u2013518 (2002)","journal-title":"SIAM J. Discrete Math."},{"issue":"2\u20133","key":"32_CR14","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, M.Y., Cheng, T.C.E.: Paired-domination in inflated graphs. Theoret. Comput. Sci. 320(2\u20133), 485\u2013494 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"32_CR15","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, S.D., Palios, L.: An $$O(n)$$-time algorithm for the paired domination problem on permutation graphs. Eur. J. Comb. 34(3), 593\u2013608 (2013)","journal-title":"Eur. J. Comb."},{"issue":"10","key":"32_CR16","doi-asserted-by":"publisher","first-page":"2809","DOI":"10.1007\/s00453-020-00705-7","volume":"82","author":"CC Lin","year":"2020","unstructured":"Lin, C.C., Ku, K.C., Hsu, C.H.: Paired-domination problem on distance-hereditary graphs. Algorithmica 82(10), 2809\u20132840 (2020)","journal-title":"Algorithmica"},{"key":"32_CR17","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.tcs.2015.05.002","volume":"591","author":"CC Lin","year":"2015","unstructured":"Lin, C.C., Tu, H.L.: A linear-time algorithm for paired-domination on circular-arc graphs. Theoret. Comput. Sci. 591, 99\u2013105 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"32_CR18","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.: Paired-domination of trees. J. Glob. Optim. 25, 43\u201354 (2003). https:\/\/doi.org\/10.1023\/A:1021338214295","journal-title":"J. Glob. Optim."},{"key":"32_CR19","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s10479-011-0962-8","volume":"210","author":"S Shen","year":"2013","unstructured":"Shen, S., Smith, J.C.: A decomposition approach for solving a broadcast domination network design problem. Ann. Oper. Res. 210, 333\u2013360 (2013)","journal-title":"Ann. Oper. Res."},{"key":"32_CR20","first-page":"181","volume":"43","author":"F Tian","year":"2009","unstructured":"Tian, F., Xu, J.M.: A note on distance domination numbers of graphs. Australas. J. Combin. 43, 181\u2013190 (2009)","journal-title":"Australas. J. Combin."},{"key":"32_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-030-95018-7_6","volume-title":"Algorithms and Discrete Applied Mathematics","author":"V Tripathi","year":"2022","unstructured":"Tripathi, V., Kloks, T., Pandey, A., Paul, K., Wang, H.-L.: Complexity of\u00a0paired domination in\u00a0AT-free and\u00a0planar graphs. In: Balachandran, N., Inkulu, R. (eds.) CALDAM 2022. LNCS, vol. 13179, pp. 65\u201377. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-95018-7_6"},{"key":"32_CR22","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1023\/A:1016783217662","volume":"18","author":"J Wu","year":"2001","unstructured":"Wu, J., Li, H.: A dominating-set-based routing scheme in ad hoc wireless networks. Telecommun. Syst. 18, 13\u201336 (2001)","journal-title":"Telecommun. Syst."},{"issue":"1\u20133","key":"32_CR23","first-page":"245","volume":"87","author":"HG Yeh","year":"1998","unstructured":"Yeh, H.G., Chang, G.J.: Weighted connected domination and Steiner trees in distance-hereditary graphs. Discrete Appl. Math. 87(1\u20133), 245\u2013253 (1998)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22105-7_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,30]],"date-time":"2023-03-30T22:05:33Z","timestamp":1680213933000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22105-7_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031221040","9783031221057"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22105-7_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shenzhen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 October 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 October 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon-conference.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"101","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"39","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"39% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}