{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T12:26:04Z","timestamp":1773231964410,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1992,12,1]],"date-time":"1992-12-01T00:00:00Z","timestamp":723168000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1992,12]]},"DOI":"10.1007\/bf01994845","type":"journal-article","created":{"date-parts":[[2005,8,11]],"date-time":"2005-08-11T03:32:06Z","timestamp":1123731126000},"page":"609-618","source":"Crossref","is-referenced-by-count":8,"title":["The weighted maximum independent set problem in permutation graphs"],"prefix":"10.1007","volume":"32","author":[{"given":"Chang-Wu","family":"Yu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gen-Huey","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01994845_CR1","doi-asserted-by":"crossref","unstructured":"M. Atallah, R. Cole, and M. Goodrich,Cascading divide-and-conquer: a technique for designing parallel algorithms, Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987, pp. 151\u2013120.","DOI":"10.1109\/SFCS.1987.12"},{"key":"BF01994845_CR2","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0166-218X(88)90064-9","volume":"21","author":"M. J. Atallah","year":"1988","unstructured":"M. J. Atallah, G. K. Manacher, and J. Urrutia,Finding a minimum independent dominating set in a permutation graph, Discrete Applied Mathematics, vol. 21, pp. 177\u2013183, 1988.","journal-title":"Discrete Applied Mathematics"},{"key":"BF01994845_CR3","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(87)90128-9","volume":"54","author":"A. Brandstadt","year":"1987","unstructured":"A. Brandstadt and D. Kratsch,On domination problems for permutation and other graphs, Theoretical Computer Science, vol. 54, pp. 181\u2013198, 1987.","journal-title":"Theoretical Computer Science"},{"key":"BF01994845_CR4","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/3-540-54029-6_186","volume":"497","author":"L. Chen","year":"1991","unstructured":"L. Chen,Logarithmic time NC algorithms for comparability graphs and circle graphs, Lecture Notes in Computer Science: Advances in Computing and Information, vol. 497, pp. 383\u2013394, 1991.","journal-title":"Lecture Notes in Computer Science: Advances in Computing and Information"},{"key":"BF01994845_CR5","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(85)90001-X","volume":"6","author":"M. Farber","year":"1985","unstructured":"M. Farber and J. M. Keil,Domination in permutation graphs, Journal of Algorithms, vol. 6, pp. 309\u2013321, 1985.","journal-title":"Journal of Algorithms"},{"key":"BF01994845_CR6","volume-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability: a Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979."},{"key":"BF01994845_CR7","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, N.Y., 1980."},{"key":"BF01994845_CR8","unstructured":"D. Helmbold and E. Mayr,Perfect and parallel algorithms, Proceedings of the International Conference on Parallel Processing, 1986, pp. 853\u2013860."},{"key":"BF01994845_CR9","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/BF01934088","volume":"28","author":"R. G. Karlsson","year":"1988","unstructured":"R. G. Karlsson and M. H. Overmars,Scanline algorithms on a grid, BIT, vol. 28, pp. 227\u2013241, 1988.","journal-title":"BIT"},{"key":"BF01994845_CR10","volume-title":"The Art of Computer Programming, vol. 1","author":"D. E. Knuth","year":"1968","unstructured":"D. E. Knuth,The Art of Computer Programming, vol. 1, Addison-Wesley, Reading, MA., 1968."},{"key":"BF01994845_CR11","doi-asserted-by":"crossref","unstructured":"D. Kozen, U. V. Vazirani, and V. V. Vazirani,NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching, Proceedings of the Fifth Conference on Foundation of Software Technology and Theoretical Computer Science, New Dehli, 1985, pp. 498\u2013503.","DOI":"10.1007\/3-540-16042-6_28"},{"key":"BF01994845_CR12","unstructured":"C. L. Liu,Introduction to Combinatorial Mathematics, McGraw-Hill, 1968."},{"key":"BF01994845_CR13","doi-asserted-by":"crossref","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A. Pnueli","year":"1971","unstructured":"A. Pnueli, A. Lempel, and S. Even,Transitive orientation of graphs and identification of permutation graphs, Can. J. Math., vol. 23, pp. 160\u2013175, 1971.","journal-title":"Can. J. Math."},{"key":"BF01994845_CR14","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"B. Schieber and U. Vishkin,On finding lowest common ancestors: simplification and parallelization, SIAM Journals on Computing, vol. 17, pp. 1253\u20131262, 1988.","journal-title":"SIAM Journals on Computing"},{"key":"BF01994845_CR15","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1137\/0214048","volume":"14","author":"J. Spinrad","year":"1985","unstructured":"J. Spinrad,On comparability and permutation graphs, SIAM Journals on Computing, vol. 14, pp. 658\u2013670, 1985.","journal-title":"SIAM Journals on Computing"},{"key":"BF01994845_CR16","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J. Spinrad","year":"1987","unstructured":"J. Spinrad, A. Brandstadt, and L. Stewart,Bipartite permutation graphs, Discrete Applied Mathematics, vol. 18, pp. 279\u2013292, 1987.","journal-title":"Discrete Applied Mathematics"},{"key":"BF01994845_CR17","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(85)90093-6","volume":"21","author":"K. J. Supowit","year":"1985","unstructured":"K. J. Supowit,Decomposing a set of points into chains, with applications to permutation and circle graphs, Information Processing Letters, vol. 21, pp. 249\u2013252, 1985.","journal-title":"Information Processing Letters"},{"key":"BF01994845_CR18","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/3-540-52921-7_60","volume":"450","author":"K. H. Tsai","year":"1990","unstructured":"K. H. Tsai and W. L. Hsu,Fast algorithms for the dominating set problem on permutation graphs, Lecture Notes in Computer Science: Algorithms, vol. 450, pp. 109\u2013117, 1990.","journal-title":"Lecture Notes in Computer Science: Algorithms"},{"key":"BF01994845_CR19","unstructured":"Y. Zhang,Parallel algorithms for problems involving directed graphs, Ph.D. Thesis, Drexel University, 1986."}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994845.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01994845\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994845","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T21:56:31Z","timestamp":1557784591000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01994845"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,12]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1992,12]]}},"alternative-id":["BF01994845"],"URL":"https:\/\/doi.org\/10.1007\/bf01994845","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,12]]}}}