{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:48:18Z","timestamp":1710344898089},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,3,15]],"date-time":"2015-03-15T00:00:00Z","timestamp":1426377600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00224-015-9616-6","type":"journal-article","created":{"date-parts":[[2015,3,14]],"date-time":"2015-03-14T05:26:02Z","timestamp":1426310762000},"page":"273-286","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Exact Algorithms for Intervalizing Coloured Graphs"],"prefix":"10.1007","volume":"58","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Johan M. M.","family":"van Rooij","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,3,15]]},"reference":[{"key":"9616_CR1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/S0012-365X(00)00257-0","volume":"235","author":"C \u00c0lvarex","year":"2001","unstructured":"\u00c0lvarex, C., D\u00edaz, J., Serna, M.: The hardness of intervalizing four colored caterpillars. Discret. Math. 235, 19\u201327 (2001)","journal-title":"Discret. Math."},{"key":"9616_CR2","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1051\/ita\/2009014","volume":"43","author":"C \u00c0lvarex","year":"2010","unstructured":"\u00c0lvarex, C., Serna, M.: On the proper intervalization of colored caterpillar trees. Informatique Th\u00e9orique et Applications 43, 667\u2013686 (2010)","journal-title":"Informatique Th\u00e9orique et Applications"},{"key":"9616_CR3","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"HL Bodlaender","year":"1990","unstructured":"Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algorithm. 11, 631\u2013643 (1990)","journal-title":"J. Algorithm."},{"key":"9616_CR4","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"9616_CR5","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., de Fluiter, B.: Intervalizing k-colored graphs. In: F\u00fcl\u00f6p, Z., G\u00e9cseg, F. (eds.) Proceedings of the 22nd International Colloquium on Automata, Languages and Programming, ICALP\u201995, Lecture Notes in Computer Science, vol. 944, pp. 87\u201398. Springer, Berlin Heidelberg New York (1995)","DOI":"10.1007\/3-540-60084-1_65"},{"key":"9616_CR6","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0166-218X(96)00057-1","volume":"71","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., de Fluiter, B.: On intervalizing k-colored graphs for DNA physical mapping. Discret. Appl. Math. 71, 55\u201377 (1996)","journal-title":"Discret. Appl. Math."},{"key":"9616_CR7","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., de Fluiter, B.L.E.: Intervalizing k-colored graphs. Technical Report UU-CS-1995-15. Department of Computer Science. Utrecht University, Utrecht (1995)","DOI":"10.1007\/3-540-60084-1_65"},{"key":"9616_CR8","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1007\/s00224-011-9312-0","volume":"50","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender, H.L., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.M.: A note on exact algorithms for vertex ordering problems on graphs. Theory Comput. Syst. 50, 420\u2013432 (2012)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9616_CR9","first-page":"12","volume":"9","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender, H.L., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.M.: On exact algorithms for treewidth. ACM Trans. Algoritm. 9(1), 12 (2012)","journal-title":"ACM Trans. Algoritm."},{"key":"9616_CR10","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithm. 21, 358\u2013402 (1996)","journal-title":"J. Algorithm."},{"key":"9616_CR11","unstructured":"Bodlaender, H.L., Nederlof, J.: Unpublished results (2015)"},{"key":"9616_CR12","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1093\/comjnl\/bxm033","volume":"51","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. Comput. J. 51, 292\u2013302 (2008)","journal-title":"Comput. J."},{"key":"9616_CR13","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Hallett, M.T., Wareham, H.T.: DNA physical mapping: three ways difficult (extended abstract). In: Lengauer, T. (ed.) Proceedings of the 1st Annual European Symposium on Algorithms, ESA\u201993, Lecture Notes in Computer Science, vol. 726, pp. 157\u2013168. Springer, Berlin Heidelberg New York (1993)","DOI":"10.1007\/3-540-57273-2_52"},{"key":"9616_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin Heidelberg New York (2010)"},{"key":"9616_CR15","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S.: Efficient computation of representative sets with applications in parameterized and exact algorithms. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pp. 142\u2013151 (2014)","DOI":"10.1137\/1.9781611973402.10"},{"key":"9616_CR16","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Thilikos, D.M.: A simple and fast approach for solving problems on planar graphs. In: Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science, STACS 2004, Lecture Notes in Computer Science, vol. 2996, pp. 56\u201367. Springer, Berlin Heidelberg New York (2004)","DOI":"10.1007\/978-3-540-24749-4_6"},{"key":"9616_CR17","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"9616_CR18","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1006\/aama.1994.1009","volume":"15","author":"MC Golumbic","year":"1994","unstructured":"Golumbic, M.C., Kaplan, H., Shamir, R.: On the complexity of DNA physical mapping. Adv. Appl. Math. 15, 251\u2013261 (1994)","journal-title":"Adv. Appl. Math."},{"key":"9616_CR19","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"MC Golumbic","year":"1995","unstructured":"Golumbic, M.C., Kaplan, H., Shamir, R.: Graph sandwich problems. J. Algorithm. 19, 449\u2013472 (1995)","journal-title":"J. Algorithm."},{"key":"9616_CR20","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Minimal interval completions. In: Proceedings of the 13th Annual European Symposium on Algorithms, ESA 2005, Lecture Notes in Computer Science, vol. 3669, pp. 403\u2013414. Springer, Berlin Heidelberg New York (2005)","DOI":"10.1007\/11561071_37"},{"key":"9616_CR21","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10, 196\u2013210 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"9616_CR22","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1007\/PL00009277","volume":"24","author":"H Kaplan","year":"1999","unstructured":"Kaplan, H., Shamir, R.: Bounded degree interval sandwich problems. Algorithmica 24, 96\u2013104 (1999)","journal-title":"Algorithmica"},{"key":"9616_CR23","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9, 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9616_CR24","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0895480192229273","volume":"7","author":"FR McMorris","year":"1994","unstructured":"McMorris, F.R., Warnow, T., Wimer, T.: Triangulating vertex-colored graphs. SIAM J. Discret. Math. 7(2), 296\u2013306 (1994)","journal-title":"SIAM J. Discret. Math."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9616-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9616-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9616-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,22]],"date-time":"2019-08-22T00:34:09Z","timestamp":1566434049000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9616-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,15]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9616"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9616-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,15]]}}}