{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:50:37Z","timestamp":1759063837949,"version":"3.41.2"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Optimization and Applications"],"published-print":{"date-parts":[[2001,1]]},"DOI":"10.1023\/a:1008791627588","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T11:37:32Z","timestamp":1040557052000},"page":"49-62","source":"Crossref","is-referenced-by-count":17,"title":["An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs"],"prefix":"10.1007","volume":"18","author":[{"given":"Mrinmoy","family":"Hota","sequence":"first","affiliation":[]},{"given":"Madhumangal","family":"Pal","sequence":"additional","affiliation":[]},{"given":"Tapan K.","family":"Pal","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"312950_CR1","unstructured":"D.G. Corneil and P.A. Kamula, \u201cExtensions of permutation and interval graphs, \u201d in Proc. 18th Southeast Conf. on Combinatorics, Graph Theory and Computing, Congr. Numer., 1987, pp. 267\u2013276."},{"key":"312950_CR2","doi-asserted-by":"crossref","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, \u201cTrapezoid graphs and their coloring, \u201d Discrete Applied Mathematics, vol. 21, pp. 35\u201346, 1988.","journal-title":"Discrete Applied Mathematics"},{"key":"312950_CR3","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0166-218X(94)00158-A","volume":"66","author":"F. Cheah","year":"1996","unstructured":"F. Cheah and D.G. Corneil, \u201cOn the structure of trapezoid graphs, \u201d Discrete Applied Mathematics, vol. 66, pp. 109\u2013133, 1996.","journal-title":"Discrete Applied Mathematics"},{"key":"312950_CR4","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/77600.77615","volume":"37","author":"R.K. Ahuja","year":"1990","unstructured":"R.K. Ahuja, K. Mehlhorn, J.B. Orlin, and R.E. Tarjan, \u201cFaster algorithms for the shortest path problem, \u201d J. ACM, vol. 37, pp. 213\u2013223, 1990.","journal-title":"J. ACM"},{"key":"312950_CR5","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0020-0190(92)90114-B","volume":"43","author":"M.S. Chang","year":"1992","unstructured":"M.S. Chang and F.-H. Wang, Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs, Information Processing Letters, vol. 43, pp. 293\u2013295, 1992.","journal-title":"Information Processing Letters"},{"key":"312950_CR6","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"J. Edmonds and R.M. Karp, \u201cTheoretical improvements in algorithmic efficiency for network flow problems, \u201d J. ACM, vol. 19, 248\u2013264, 1972.","journal-title":"J. ACM"},{"key":"312950_CR7","volume-title":"Computer and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computer and Intractability: A Guide to the Theory of NP-Completeness, Freeman: San Francisco, CA, 1979."},{"key":"312950_CR8","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":"312950_CR9","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1080\/00207169908804777","volume":"70","author":"M. Hota","year":"1999","unstructured":"M. Hota, M. Pal, and T.K. Pal, \u201cAn efficient algorithm to generate all maximal independent sets on trapezoid graphs, \u201d Intern. J. Computer Mathematics, vol. 70, pp. 587\u2013599, 1999.","journal-title":"Intern. J. Computer Mathematics"},{"key":"312950_CR10","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0020-0190(91)90124-Z","volume":"40","author":"J.Y. Hsiao","year":"1991","unstructured":"J.Y. Hsiao, C.Y. Tang, and R.S. Chang, \u201cSolving the single step graph searching problem by solving the maximum two-independent set problem, \u201d Information Processing Letters, vol. 40, pp. 283\u2013287, 1991.","journal-title":"Information Processing Letters"},{"key":"312950_CR11","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(92)90216-I","volume":"43","author":"J.Y. Hsiao","year":"1992","unstructured":"J.Y. Hsiao, C.Y. Tang, and R.S. Chang, \u201cAn efficient algorithm for finding a maximum weight 2-independent set on interval graphs, \u201d Information Processing Letters, vol. 43, pp. 229\u2013235, 1992.","journal-title":"Information Processing Letters"},{"key":"312950_CR12","unstructured":"W.L. Hsu and K.H. Tsai, \u201cA linear time algorithm for the two-track assignment problem, \u201d in Proceedings of 27th Allerton Conf. on Communication, Control and Computing, 1989, pp. 291\u2013300."},{"key":"312950_CR13","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D.S. Johnson","year":"1985","unstructured":"D.S. Johnson, \u201cThe NP-completeness column: An on going guide, \u201d J. Algorithms, vol. 6, pp. 434\u2013451, 1985.","journal-title":"J. Algorithms"},{"key":"312950_CR14","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1137\/0405022","volume":"5","author":"R.D. Lou","year":"1992","unstructured":"R.D. Lou, M. Sarrafgadeh, and D.T. Lee, \u201cAn optimal algorithm for the maximum two-chain problem, \u201d SIAM J. Discrete Math., vol. 5, pp. 285\u2013304, 1992.","journal-title":"SIAM J. Discrete Math."},{"key":"312950_CR15","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1006\/jagm.1994.1034","volume":"17","author":"T.H. Ma","year":"1994","unstructured":"T.H. Ma and J.P. Spinrad, \u201cOn the 2-chain subgraph cover and related problems, \u201d J. Algorithms, vol. 17, pp. 251\u2013268, 1994.","journal-title":"J. Algorithms"},{"key":"312950_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1080\/00207169608804486","volume":"60","author":"M. Pal","year":"1996","unstructured":"M. Pal and G.P. Bhattacharjee, \u201cA sequential algorithm for finding a maximum weight k-independent set on interval graphs, \u201d Intern. J. Comput. Math., vol. 60, pp. 205\u2013214, 1996.","journal-title":"Intern. J. Comput. Math."},{"key":"312950_CR17","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1109\/43.31548","volume":"8","author":"M. Sarrafgadeh","year":"1989","unstructured":"M. Sarrafgadeh and D.T. Lee, \u201cA new approach to topological via minimization, \u201d IEEE Trans. Computer Aided Design, vol. 8, pp. 890\u2013900, 1989.","journal-title":"IEEE Trans. Computer Aided Design"},{"key":"312950_CR18","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M. Yannakakis","year":"1987","unstructured":"M. Yannakakis and F. Gavril, \u201cThe maximum k-colourable subgraph problem for chordal graphs, \u201d Information Processing Letters, vol. 24, pp. 133\u2013137, 1987.","journal-title":"Information Processing Letters"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1008791627588.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1008791627588\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1008791627588.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,13]],"date-time":"2025-07-13T03:20:57Z","timestamp":1752376857000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1008791627588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["312950"],"URL":"https:\/\/doi.org\/10.1023\/a:1008791627588","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}