{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:58Z","timestamp":1759639078295,"version":"3.37.3"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["106-2221-E-027-025"],"award-info":[{"award-number":["106-2221-E-027-025"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:p> Counting dominating sets (DSs) in a graph is a #P-complete problem even for chordal bipartite graphs and split graphs, which are both subclasses of weakly chordal graphs. This paper investigates this problem for distance-hereditary graphs, which is another known subclass of weakly chordal graphs. This work develops linear-time algorithms for counting DSs and their two variants, total DSs and connected DSs in distance-hereditary graphs. <\/jats:p>","DOI":"10.1142\/s1793830921500129","type":"journal-article","created":{"date-parts":[[2020,8,29]],"date-time":"2020-08-29T08:41:22Z","timestamp":1598690482000},"page":"2150012","source":"Crossref","is-referenced-by-count":0,"title":["Fast and simple algorithms for counting dominating sets in distance-hereditary graphs"],"prefix":"10.1142","volume":"13","author":[{"given":"Min-Sheng","family":"Lin","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, National Taipei University of Technology, Taipei 10608, Taiwan"}]}],"member":"219","published-online":{"date-parts":[[2020,10,5]]},"reference":[{"issue":"2","key":"S1793830921500129BIB001","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"Bandelt H. J.","year":"1986","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"S1793830921500129BIB002","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1002\/(SICI)1097-0037(199805)31:3<177::AID-NET4>3.0.CO;2-C","volume":"31","author":"Brandst\u00e4dt A.","year":"1998","journal-title":"Networks"},{"key":"S1793830921500129BIB003","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"Brandst\u00e4dt A.","year":"1999"},{"issue":"1","key":"S1793830921500129BIB004","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/S0166-218X(99)00146-8","volume":"99","author":"Broersma H. J.","year":"2000","journal-title":"Discrete Appl. Math."},{"key":"S1793830921500129BIB005","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1007\/3-540-63890-3_37","volume-title":"Int. Symp. Algorithms and Computation","author":"Chang M. S.","year":"1997"},{"issue":"1","key":"S1793830921500129BIB006","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0166-218X(00)00330-9","volume":"116","author":"Chang M. S.","year":"2002","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"S1793830921500129BIB007","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.disopt.2005.03.004","volume":"2","author":"Cogis O.","year":"2005","journal-title":"Discrete Optim."},{"issue":"3","key":"S1793830921500129BIB008","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1137\/0217032","volume":"17","author":"D\u2019Atri A.","year":"1988","journal-title":"SIAM J. Comput."},{"issue":"4","key":"S1793830921500129BIB009","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1093\/qmath\/28.4.417","volume":"28","author":"Howorka E.","year":"1977","journal-title":"Q. J. Math."},{"issue":"9","key":"S1793830921500129BIB010","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1109\/TPDS.2002.1036071","volume":"13","author":"Hsieh S. Y.","year":"2002","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"3","key":"S1793830921500129BIB011","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1016\/j.dam.2005.07.012","volume":"154","author":"Hsieh S. Y.","year":"2006","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"S1793830921500129BIB012","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/j.tcs.2005.04.009","volume":"341","author":"Hung R. W.","year":"2005","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"S1793830921500129BIB013","doi-asserted-by":"crossref","first-page":"1142","DOI":"10.1137\/S0097539793304601","volume":"27","author":"Hunt H. B.","year":"1998","journal-title":"SIAM J. Comput."},{"key":"S1793830921500129BIB014","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/978-3-642-22685-4_2","volume-title":"Int. Computing and Combinatorics Conf.","author":"Kijima S.","year":"2011"},{"key":"S1793830921500129BIB015","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.dam.2017.12.023","volume":"239","author":"Lin M. S.","year":"2018","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"S1793830921500129BIB016","first-page":"163","volume":"117","author":"Lu C. L.","year":"2002","journal-title":"Discrete Appl. Math."},{"key":"S1793830921500129BIB017","first-page":"141","volume-title":"3rd Int. Colloquium on Structural Information and Communication Complexity (SIROCCO\u201996)","author":"Stefano G. D.","year":"1997"},{"issue":"3","key":"S1793830921500129BIB018","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"Valiant L. G.","year":"1979","journal-title":"SIAM J. Comput."}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830921500129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T16:56:55Z","timestamp":1612803415000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830921500129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,5]]},"references-count":18,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["10.1142\/S1793830921500129"],"URL":"https:\/\/doi.org\/10.1142\/s1793830921500129","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2020,10,5]]}}}