{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:10:11Z","timestamp":1725495011575},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540653882"},{"type":"electronic","value":"9783540493662"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49366-2_10","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T13:48:47Z","timestamp":1194961727000},"page":"113-124","source":"Crossref","is-referenced-by-count":0,"title":["An Optimal Parallel Algorithm for the Perfect Dominating Set Problem on Distance-Hereditary Graphs"],"prefix":"10.1007","author":[{"given":"Sun-Yuan","family":"Hsieh","sequence":"first","affiliation":[]},{"given":"Gen-Huey","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Chin-Wen","family":"Ho","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1998,11,30]]},"reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K. Abrahamson","year":"1989","unstructured":"K. Abrahamson, N. Dadoun, D. G. Kirkpatrick, and T. Przytycka, A simple parallel tree contraction algorithm. Journal of Algorithms., 10, pp. 287\u2013302, 1989.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"10_CR2","first-page":"182","volume":"41","author":"H. J. Bandelt","year":"1989","unstructured":"H. J. Bandelt and H. M. Mulder. Distance-hereditary graphs. Journal of Combinatorial Theory Series B, 41(1):182\u2013208, Augest 1989.","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"10_CR3","volume-title":"Graphs and hypergraphs","author":"C. Berge","year":"1973","unstructured":"C. Berge. Graphs and hypergraphs. North-Holland, Amsterdam, 1973."},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0095-8956(73)90042-7","volume":"15","author":"N. Biggs","year":"1973","unstructured":"N. Biggs. Perfect codes in graphs. J. Combin. Theory Ser. B, 15:289\u2013296, 1973.","journal-title":"J. Combin. Theory Ser. B"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/(SICI)1097-0037(199805)31:3<177::AID-NET4>3.0.CO;2-C","volume":"31","author":"A. Brandst\u00e4dt","year":"1998","unstructured":"A. Brandst\u00e4dt and F. F. Dragan, A linear time algorithm for connected \u03b3-domination and Steiner tree on distance-hereditary graphs, Networks, 31:177\u2013182, 1998.","journal-title":"Networks"},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0020-0190(93)90147-2","volume":"48","author":"M. S. Chang","year":"1993","unstructured":"M. S. Chang and Y. C. Liu. Polynomial algorithm for the weighted perfect domination problems on chordal graphs and split graphs. Information Processing Letters, 48:205\u2013210, 1993.","journal-title":"Information Processing Letters"},{"key":"10_CR7","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0166-218X(94)00067-3","volume":"63","author":"G. J. Chang","year":"1995","unstructured":"G. J. Chang, C. Pandu Rangan, and S. R. Coorg. Weighted independent perfect domination on cocomparability graphs. Discrete Applied Mathematics, 63:215\u2013222, 1995.","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1007\/3-540-63890-3_37","volume-title":"Proceedings of 7th International Symposium on Algorithms and Computation, ISAAC\u201997","author":"M. S. Chang","year":"1997","unstructured":"M. S. Chang, S. Y. Hsieh, and G. H. Chen. Dynamic Programming on Distance-Hereditary Graphs. Proceedings of 7th International Symposium on Algorithms and Computation, ISAAC\u201997, LNCS 1350, pp. 344\u2013353."},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, \u201cOptimal (parallel) algorithms for the all-to-all vertices distance problem for certain graph classes,\u201d Lecture notes in computer science 726, pp. 60\u201369.","DOI":"10.1007\/3-540-56402-0_36"},{"issue":"1","key":"10_CR10","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0166-218X(93)E0138-O","volume":"57","author":"E. Dahlhaus","year":"1995","unstructured":"E. Dahlhaus. Efficient parallel recognition algorithms of cographs and distance-hereditary graphs. Discrete applied mathematics, 57(1):29\u201344, February 1995.","journal-title":"Discrete applied mathematics"},{"issue":"3","key":"10_CR11","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1137\/0217032","volume":"17","author":"A. D\u2019atri","year":"1988","unstructured":"A. D\u2019atri and M. Moscarini. Distance-hereditary graphs, steiner trees, and connected domination. SIAM Journal on Computing, 17(3):521\u2013538, June, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"10_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1007\/3-540-58218-5_34","volume-title":"Algorithm Theory-SWAT\u201994 \u201c4th Scandinavian Workshop on Algorithm Theory","author":"F. F. Dragan","year":"1994","unstructured":"F. F. Dragan, Dominating cliques in distance-hereditary graphs, Algorithm Theory-SWAT\u201994 \u201c4th Scandinavian Workshop on Algorithm Theory, LNCS 824, Springer, Berlin, pp. 370\u2013381, 1994."},{"key":"10_CR13","volume-title":"Algorithmic graph theory and perfect graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic. Algorithmic graph theory and perfect graphs, Academic press, New York, 1980."},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"P. L. Hammer and F. Maffray. Complete separable graphs. Discrete applied mathematics, 27(1):85\u201399, May 1990.","DOI":"10.1016\/0166-218X(90)90131-U"},{"key":"10_CR15","unstructured":"X. He. Efficient parallel algorithms for solving some tree problems. Proc. 24th Allerton Conference on Communication, Control, and Computing, 777\u2013786, 1986."},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1016\/0196-6774(91)90012-N","volume":"12","author":"X. He","year":"1991","unstructured":"X. He. Efficient parallel algorithms for series-parallel graphs. Journal of Algorithms, 12:409\u2013430, 1991.","journal-title":"Journal of Algorithms"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0196-6774(88)90007-7","volume":"9","author":"X. He","year":"1988","unstructured":"X. He and Y. Yesha. Binary tree algebraic computation and parallel algorithms for simple graphs. Journal of Algorithms, 9:92\u2013113, 1988.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"10_CR18","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1093\/qmath\/28.4.417","volume":"28","author":"E. Howorka","year":"1977","unstructured":"E. Howorka. A characterization of distance-hereditary graphs. Quarterly Journal of Mathematics (Oxford), 28(2):417\u2013420. 1977.","journal-title":"Quarterly Journal of Mathematics (Oxford)"},{"key":"10_CR19","unstructured":"S.-y. Hsieh, C. W. Ho, T.-s. Hsu, M. T. Ko, and G. H. Chen. Efficient parallel algorithms on distance-hereditary graphs. Parallel Processing Letters, to appear. A preliminary version of this paper is in Proceedings of the International Conference on Parallel Processing, pp. 20\u201323, 1997."},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"S.-y. Hsieh, Parallel decomposition of Distance-Hereditary Graphs with its application. Manuscript, 1998.","DOI":"10.1007\/3-540-49164-3_40"},{"key":"10_CR21","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of Irregular\u201998","author":"S.-y. Hsieh","year":"1998","unstructured":"S.-y. Hsieh, C. W. Ho, T.-s. Hsu, M. T. Ko, and G. H. Chen. A new simple tree contraction scheme and its application on distance-hereditary graphs. Proceedings of Irregular\u201998, LNCS, Springer-Verlag, to appear."},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"S.-y. Hsieh, C. W. Ho, T.-s. Hsu, M. T. Ko, and G. H. Chen. Characterization of efficiently solvable problems on distance-hereditary Graphs. Proceedings of 8th International Symposium on Algorithms and Computation, ISAAC\u201998, Springer-Verlag, to appear.","DOI":"10.1007\/3-540-49381-6_28"},{"key":"10_CR23","first-page":"187","volume":"79","author":"M. Livingston","year":"1990","unstructured":"M. Livingston and Q. F. Stout. Perfect dominating sets. Congr. Numer., 79:187\u2013203, 1990.","journal-title":"Congr. Numer."},{"key":"10_CR24","unstructured":"Falk Nicolai. Hamiltonian problems on distance-hereditary graphs. Technique report, Gerhard-Mercator University, Germany, 1994."}],"container-title":["Lecture Notes in Computer Science","Advances in Computing Science ASIAN 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49366-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T06:17:06Z","timestamp":1556950626000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49366-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540653882","9783540493662"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-49366-2_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}