{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:49:58Z","timestamp":1759063798557},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540653851"},{"type":"electronic","value":"9783540493815"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49381-6_29","type":"book-chapter","created":{"date-parts":[[2007,12,3]],"date-time":"2007-12-03T06:47:50Z","timestamp":1196664470000},"page":"267-275","source":"Crossref","is-referenced-by-count":9,"title":["Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphs"],"prefix":"10.1007","author":[{"given":"Yaw-Ling","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,3,29]]},"reference":[{"key":"29_CR1","unstructured":"K. Arvind and C. Pandu Rangan. Efficient algorithms for domination problems on cocomparability graphs. Manuscript, 1990."},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF01553888","volume":"4","author":"M. J. Atallah","year":"1989","unstructured":"M. J. Atallah and S. R. Kosaraju. An efficient algorithm for maxdominance, with applications. Algorithmica, 4:221\u2013236, 1989.","journal-title":"Algorithmica"},{"key":"29_CR3","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":"29_CR4","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0166-218X(97)80001-7","volume":"80","author":"M.-S. Chang","year":"1997","unstructured":"M.-S. Chang. Weighted domination of cocomparability graphs. Discr. Applied Math., 80:135\u2013148, 1997.","journal-title":"Discr. Applied Math."},{"key":"29_CR5","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(88)90032-7","volume":"21","author":"I. Dagan","year":"1988","unstructured":"I. Dagan, M.C. Golumbic, and R.Y. Pinter. Trapezoid graphs and their coloring. Discr. Applied Math., 21:35\u201346, 1988.","journal-title":"Discr. Applied Math."},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Felsner, Muller, and Wernisch. Trapezoid graphs and generalizations, geometry and algorithms. Discr. Applied Math., 74, 1997.","DOI":"10.1016\/S0166-218X(96)00013-3"},{"key":"29_CR7","volume-title":"Fundamentals of Domination in Graphs.","author":"T.W. Haynes","year":"1998","unstructured":"T.W. Haynes, S.T. Hedetniemi, and P.J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, Inc., N. Y., 1998."},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Y. D. Liang, C.-L. Lu, and C.-Y. Tang. Efficient domination on permutation graphs and trapezoid graphs. In COCOON\u201997, pages 232\u2013241, 1997.","DOI":"10.1007\/BFb0045090"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Y. Daniel Liang. Dominations in trapezoid graphs. Information Processing Letters, 52(6):309\u2013315, December 1994.","DOI":"10.1016\/0020-0190(94)00159-6"},{"key":"29_CR10","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":"29_CR11","unstructured":"T.-H. Ma and J.P. Spinrad. An O(n2) time algorithm for the 2-chain cover problem and related problems. In Proc. 2nd ACM-SIAM Symp. Discrete Algorithms, pages 363\u2013372, 1991."},{"key":"29_CR12","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M. H. Overmars","year":"1981","unstructured":"M. H. Overmars and J. van Leeuwen. Maintenance of configuration in the plane. Journal of Computer and Systems Science, 23:166\u2013204, 1981.","journal-title":"Journal of Computer and Systems Science"},{"key":"29_CR13","unstructured":"Anand Srinivasan, M.S. Chang, K. Madhukar, and C. Pandu Rangan. Efficient algorithms for the weighted domination problems on trapezoid graphs. Manuscript, 1996."},{"key":"29_CR14","unstructured":"G. Steiner. Polynomial time algorithm for finding a Hamiltonian cycle in the incomparability graph. Manuscript, 1992."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49381-6_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,5]],"date-time":"2019-05-05T13:10:24Z","timestamp":1557061824000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49381-6_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540653851","9783540493815"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-49381-6_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}