{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:17Z","timestamp":1759638497398},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600848"},{"type":"electronic","value":"9783540494256"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60084-1_65","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:39:56Z","timestamp":1330277996000},"page":"87-98","source":"Crossref","is-referenced-by-count":11,"title":["Intervalizing k-colored graphs"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Babette","family":"Fluiter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"8_CR1","first-page":"449","volume-title":"Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy","author":"H. L. Bodlaender","year":"1994","unstructured":"H. L. Bodlaender, M. R. Fellows, and M. Hallett. Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy. In Proceedings of the 26th Annual Symposium on Theory of Computing, pages 449\u2013458, New York, 1994. ACM Press."},{"key":"8_CR2","first-page":"273","volume-title":"Lecture Notes in Computer Science, vol. 623","author":"H. L. Bodlaender","year":"1992","unstructured":"H. L. Bodlaender, M. R. Fellows, and T. J. Warnow. Two strikes against perfect phylogeny. In Proceedings 19th International Colloquium on Automata, Languages and Programming, pages 273\u2013283, Berlin, 1992. Springer Verlag, Lecture Notes in Computer Science, vol. 623."},{"key":"8_CR3","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1006\/jagm.1993.1035","volume":"15","author":"H. L. Bodlaender","year":"1993","unstructured":"H. L. Bodlaender and T. Kloks. A simple linear time algorithm for triangulating three-colored graphs. J. Algorithms, 15:160\u2013172, 1993.","journal-title":"J. Algorithms"},{"key":"8_CR4","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"J. A. Ellis","year":"1994","unstructured":"J. A. Ellis, I. H. Sudborough, and J. Turner. The vertex separation and search number of a graph. Information and Computation, 113:50\u201379, 1994.","journal-title":"Information and Computation"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"M. R. Fellows, M. T. Halett, and H. T. Wareham. DNA physical mapping: Three ways difficult (extended abstract). In T. Lengauer, editor, Proceedings 1st Annual European Symposium on Algorithms ESA '93, pages 157\u2013168. Springer Verlag, Lecture Notes in Computer Science, vol. 726, 1993.","DOI":"10.1007\/3-540-57273-2_52"},{"key":"8_CR6","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1006\/aama.1994.1009","volume":"15","author":"M. C. Golumbic","year":"1994","unstructured":"M. C. Golumbic, H. Kaplan, and R. Shamir. On the complexity of dna physical mapping. Advances in Applied Mathematics, 15:251\u2013261, 1994.","journal-title":"Advances in Applied Mathematics"},{"key":"8_CR7","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/0406023","volume":"2","author":"R. Idury","year":"1993","unstructured":"R. Idury and A. Schaffer. Triangulating three-colored graphs in linear time and linear space. SIAM J. Disc. Meth., 2:289\u2013293, 1993.","journal-title":"SIAM J. Disc. Meth."},{"key":"8_CR8","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1137\/0405019","volume":"5","author":"S. Kannan","year":"1992","unstructured":"S. Kannan and T. Warnow. Triangulating 3-colored graphs. SIAM J. Disc. Meth., 5:249\u2013258, 1992.","journal-title":"SIAM J. Disc. Meth."},{"key":"8_CR9","volume-title":"Technical Report 285\/93","author":"H. Kaplan","year":"1993","unstructured":"H. Kaplan and R. Shamir. Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques. Technical Report 285\/93, Inst. for Computer Science, Tel Aviv University, Tel Aviv, Israel, 1993. To appear in SIAM J. Comput."},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"H. Kaplan, R. Shamir, and R. E. Tarjan. Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping. In Proceedings of the 35th annual symposium on Foundations of Computer Science (FOCS), pages 780\u2013791. IEEE Computer Science Press, 1994.","DOI":"10.1109\/SFCS.1994.365715"},{"issue":"2","key":"8_CR11","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0895480192229273","volume":"7","author":"F. R. McMorris","year":"1994","unstructured":"F. R. McMorris, T. Warnow, and T. Wimer. Triangulating vertex-colored graphs. SIAM J. Disc. Meth., 7(2):296\u2013306, 1994.","journal-title":"SIAM J. Disc. Meth."},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"R. H. M\u00f6hring. Graph problems related to gate matrix layout and PLA folding. In E. Mayr, H. Noltemeier, and M. Sys\u0142o, editors, Computational Graph Theory, Comuting Suppl. 7, pages 17\u201351. Springer Verlag, 1990.","DOI":"10.1007\/978-3-7091-9076-0_2"},{"issue":"3","key":"8_CR13","first-page":"543","volume":"377-A","author":"S.-I. Nakano","year":"1994","unstructured":"S.-I. Nakano, T. Oguma, and T. Nishizeki. A linear time algorithm for c-triangulating three-colored graphs. Trans. Institute of Electronics, Information and Communication, Eng., A., 377-A(3):543\u2013546, 1994. In Japanese.","journal-title":"Trans. Institute of Electronics, Information and Communication, Eng., A."},{"key":"8_CR14","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1137\/0601042","volume":"1","author":"J. B. Saxe","year":"1980","unstructured":"J. B. Saxe. Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Alg. Disc. Meth., 1:363\u2013369, 1980.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"8_CR15","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M. Steel","year":"1992","unstructured":"M. Steel. The complexity of reconstructing trees from qualitative characters and subtrees. J. of Classification, 9:91\u2013116, 1992.","journal-title":"J. of Classification"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60084-1_65.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:54:39Z","timestamp":1605646479000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60084-1_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600848","9783540494256"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-60084-1_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}