{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T06:46:43Z","timestamp":1726037203677},"publisher-location":"Singapore","reference-count":32,"publisher":"Springer Singapore","isbn-type":[{"type":"print","value":"9789811391897"},{"type":"electronic","value":"9789811391903"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-981-13-9190-3_54","type":"book-chapter","created":{"date-parts":[[2019,7,10]],"date-time":"2019-07-10T17:02:55Z","timestamp":1562778175000},"page":"495-502","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Paired-Domination Problem on Distance Hereditary Graphs"],"prefix":"10.1007","author":[{"given":"Ching-Chi","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keng-Chu","family":"Ku","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gen-Huey","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chan-Hung","family":"Hsu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,11]]},"reference":[{"key":"54_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial \n                    \n                      \n                    \n                    $$k$$\n                  -trees. Discrete Appl. Math. 23, 11\u201324 (1989)","journal-title":"Discrete Appl. Math."},{"key":"54_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Marchetti-Spaccamela, A., Crescenzi, P., Gambosi, G., Protasi, M., Kann, V.: Complexity and Approximation. Springer, Berlin (1999). \n                    https:\/\/doi.org\/10.1007\/978-3-642-58412-1"},{"key":"54_CR3","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"HJ Bandelt","year":"1986","unstructured":"Bandelt, H.J., Mulder, H.M.: Distance-hereditary graphs. J. Comb. Theory Series B 41, 182\u2013208 (1986)","journal-title":"J. Comb. Theory Series B"},{"key":"54_CR4","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","volume":"19","author":"AA Bertossi","year":"1984","unstructured":"Bertossi, A.A.: Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19, 37\u201340 (1984)","journal-title":"Inf. Process. Lett."},{"key":"54_CR5","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0020-0190(86)90112-2","volume":"23","author":"AA Bertossi","year":"1986","unstructured":"Bertossi, A.A.: Total domination in interval graphs. Inf. Process. Lett. 23, 131\u2013134 (1986)","journal-title":"Inf. Process. Lett."},{"key":"54_CR6","unstructured":"Beyer, T., Proskurowski, A., Hedetniemi, S., Mitchell, S.: Independent domination in trees. In: The Proceedings of SEICCGTC 1977, pp. 321\u2013328 (1977)"},{"key":"54_CR7","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/0211015","volume":"11","author":"KS 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":"54_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BFb0028791","volume-title":"Fundamentals of Computation Theory","author":"A Brandst\u00e4dt","year":"1985","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On the restriction of some NP-complete graph problems to permutation graphs. In: Budach, L. (ed.) FCT 1985. LNCS, vol. 199, pp. 53\u201362. Springer, Heidelberg (1985). \n                    https:\/\/doi.org\/10.1007\/BFb0028791"},{"key":"54_CR9","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0166-218X(88)90120-5","volume":"22","author":"G Chang","year":"1988","unstructured":"Chang, G.: Labeling algorithms for domination problems in sun-free chordal graphs. Discrete Appl. Math. 22, 21\u201334 (1988)","journal-title":"Discrete Appl. Math."},{"key":"54_CR10","doi-asserted-by":"publisher","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"MS Chang","year":"1998","unstructured":"Chang, M.S.: Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27, 1671\u20131694 (1998)","journal-title":"SIAM J. Comput."},{"key":"54_CR11","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). \n                    https:\/\/doi.org\/10.1007\/3-540-63890-3_37"},{"key":"54_CR12","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, 103\u2013113 (2002)","journal-title":"Discrete Appl. Math."},{"key":"54_CR13","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.H., Zeng, Z.B.: A linear-time algorithm for paired-domination problem in strongly chordal graphs. Inf. Process. Lett. 110, 20\u201323 (2009)","journal-title":"Inf. Process. Lett."},{"key":"54_CR14","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.H., Zeng, Z.B.: Labeling algorithms for paired-domination problems in block and interval graphs. J. Comb. Optim. 19, 457\u2013470 (2010)","journal-title":"J. Comb. Optim."},{"key":"54_CR15","doi-asserted-by":"publisher","first-page":"2077","DOI":"10.1016\/j.dam.2007.05.011","volume":"155","author":"TCE Cheng","year":"2007","unstructured":"Cheng, T.C.E., Kang, L., Ng, C.T.: Paired domination on interval and circular-arc graphs. Discrete Appl. Math. 155, 2077\u20132086 (2007)","journal-title":"Discrete Appl. Math."},{"key":"54_CR16","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0020-0190(75)90011-3","volume":"4","author":"E Cockayne","year":"1975","unstructured":"Cockayne, E.: A linear algorithm for the domination number of a tree. Inf. Process. Lett. 4, 41\u201344 (1975)","journal-title":"Inf. Process. Lett."},{"key":"54_CR17","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","volume":"9","author":"DG Corneil","year":"1984","unstructured":"Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discrete Appl. Math. 9, 27\u201339 (1984)","journal-title":"Discrete Appl. Math."},{"key":"54_CR18","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/0167-6377(82)90015-3","volume":"1","author":"M Farber","year":"1982","unstructured":"Farber, M.: Independent domination in chordal graphs. Oper. Res. Lett. 1, 134\u2013138 (1982)","journal-title":"Oper. Res. Lett."},{"key":"54_CR19","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0166-218X(84)90061-1","volume":"7","author":"M Farber","year":"1984","unstructured":"Farber, M.: Domination, independent domination, and duality in strongly chordal graphs. Discrete Appl. Math. 7, 115\u2013130 (1984)","journal-title":"Discrete Appl. Math."},{"key":"54_CR20","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(85)90001-X","volume":"6","author":"M Farber","year":"1985","unstructured":"Farber, M.: Domination in permutation graphs. J. Algorithms 6, 309\u2013321 (1985)","journal-title":"J. Algorithms"},{"key":"54_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR 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":"54_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(90)90131-U","volume":"27","author":"PL Hammer","year":"1990","unstructured":"Hammer, P.L., Maffray, F.: Completely separable graphs. Discrete Appl. Math. 27, 85\u201399 (1990)","journal-title":"Discrete Appl. Math."},{"key":"54_CR23","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":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Slater, P.J.: Paired domination in graphs. Networks 32, 199\u2013206 (1998)","journal-title":"Networks"},{"key":"54_CR24","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.dam.2014.01.019","volume":"170","author":"MA Henning","year":"2014","unstructured":"Henning, M.A., McCoy, J., Southey, J.: Graphs with maximum size and given paired-domination number. Discrete Appl. Math. 170, 72\u201382 (2014)","journal-title":"Discrete Appl. Math."},{"key":"54_CR25","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0166-218X(93)90178-Q","volume":"42","author":"JM Keil","year":"1993","unstructured":"Keil, J.M.: The complexity of domination problems in circle graphs. Discrete Appl. Math. 42, 51\u201363 (1993)","journal-title":"Discrete Appl. Math."},{"key":"54_CR26","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 \n                    \n                      \n                    \n                    $$O(n)$$\n                  -time algorithm for the paired domination problem on permutation graphs. Eur. J. Comb. 34, 593\u2013608 (2013)","journal-title":"Eur. J. Comb."},{"key":"54_CR27","unstructured":"Laskar, R., Pfaff, J.: Domination and irredundance in split graphs. Technical Report 430, Clemson University (1983)"},{"key":"54_CR28","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1137\/0605040","volume":"5","author":"R Laskar","year":"1984","unstructured":"Laskar, R., Pfaff, J., Hedetniemi, S.M., Hedetniemi, S.T.: On the algorithmic complexity of total domination. SIAM J. Algebraic Discrete Methods 5, 420\u2013425 (1984)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"54_CR29","unstructured":"Pfaff, J., Laskar, R., Hedetniemi, S.T.: NP-completeness of total and connected domination and irredundance for bipartite graphs. Technical Report 428, Clemson University (1983)"},{"key":"54_CR30","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. Global Optim. 25, 43\u201354 (2003)","journal-title":"J. Global Optim."},{"key":"54_CR31","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1002\/net.3230150109","volume":"15","author":"K White","year":"1985","unstructured":"White, K., Farber, M., Pulleyblank, W.: Steiner trees, connected domination and strongly chordal graphs. Networks 15, 109\u2013124 (1985)","journal-title":"Networks"},{"key":"54_CR32","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0166-218X(98)00060-2","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, 245\u2013253 (1998)","journal-title":"Discrete Appl. Math."}],"container-title":["Communications in Computer and Information Science","New Trends in Computer Technologies and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-13-9190-3_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,10]],"date-time":"2019-07-10T17:08:06Z","timestamp":1562778486000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-981-13-9190-3_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9789811391897","9789811391903"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-981-13-9190-3_54","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"11 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Symposium","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Yunlin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"incosy2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/ics2018.yuntech.edu.tw\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}