{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T16:11:02Z","timestamp":1746115862000,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642380358"},{"type":"electronic","value":"9783642380365"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38036-5_5","type":"book-chapter","created":{"date-parts":[[2013,5,13]],"date-time":"2013-05-13T02:16:04Z","timestamp":1368411364000},"page":"5-16","source":"Crossref","is-referenced-by-count":0,"title":["The Radiation Hybrid Map Construction Problem Is FPT"],"prefix":"10.1007","author":[{"given":"Iyad","family":"Kanj","sequence":"first","affiliation":[]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"5_CR1","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. Bodlaender","year":"1996","unstructured":"Bodlaender, H.: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM Journal on Computing\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"5_CR2","first-page":"49","volume":"11","author":"H. Bodlaender","year":"1995","unstructured":"Bodlaender, H., Fellows, M., Hallett, M., Wareham, H.: Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences\u00a011, 49\u201357 (1995)","journal-title":"Computer Applications in the Biosciences"},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","volume":"147","author":"H. Bodlaender","year":"1995","unstructured":"Bodlaender, H., Fellows, M., Hallett, M., Wareham, H.: The parameterized complexity of the longest common subsequence problem. Theoretical Computer Science\u00a0147, 31\u201354 (1995)","journal-title":"Theoretical Computer Science"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-540-28639-4_4","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2004","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Computing Small Search Numbers in Linear Time. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 37\u201348. Springer, Heidelberg (2004)"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Cesati, M., Wareham, H.: Parameterized complexity analysis in robot motion planning. In: Proceedings of the 25th IEEE International Conference on Systems, Man and Cybernetics, pp. 880\u2013885 (1995)","DOI":"10.1109\/ICSMC.1995.537878"},{"issue":"4","key":"5_CR6","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1007\/s00453-010-9389-x","volume":"60","author":"Z.-Z. Chen","year":"2011","unstructured":"Chen, Z.-Z., Lin, G., Wang, L.: An approximation algorithm for the minimum co-path set problem. Algorithmica\u00a060(4), 969\u2013986 (2011)","journal-title":"Algorithmica"},{"key":"5_CR7","unstructured":"Cheng, Y., Cai, Z., Goebel, R., Lin, G., Zhu, B.: The radiation hybrid map construction problem: recognition, hardness, and approximation algorithms (2008) (unpublished manuscript)"},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1126\/science.2218528","volume":"250","author":"D. Cox","year":"1990","unstructured":"Cox, D., Burmeister, M., Price, E., Kim, S., Myers, R.: Radiation hybrid mapping: a somatic cell genetic method for constructing high resolution maps of mammalian chromosomes. Science\u00a0250, 245\u2013250 (1990)","journal-title":"Science"},{"issue":"8","key":"5_CR9","doi-asserted-by":"publisher","first-page":"1703","DOI":"10.1093\/bioinformatics\/bti222","volume":"21","author":"S. De Givry","year":"2005","unstructured":"De Givry, S., Bouchez, M., Chabrier, P., Milan, D., Schiex, T.: Carh ta Gene: multipopulation integrated genetic and radiation hybrid mapping. Bioinformatics\u00a021(8), 1703 (2005)","journal-title":"Bioinformatics"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Downey, R., Evans, P., Fellows, M.: Parameterized learning complexity. In: Proceedings of the 6th ACM Workshop on Computational Learning Theory, pp. 51\u201357 (1993)","DOI":"10.1145\/168304.168311"},{"key":"5_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized complexity. Springer, New York (1999)"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M., Stege, U.: Parameterized complexity: a framework for systematically confronting computational intractability. In: Roberts, F., Kratochvil, J., Ne\u0161et\u0159il, J. (eds.) Contemporary Trends in Discrete Mathematics, AMS-DIMACS Proceedings, pp. 49\u201399. American Mathematical Society (1999)","DOI":"10.1090\/dimacs\/049\/04"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Faraut, T., De Givry, S., Chabrier, P., Derrien, T., Galibert, F., Hitte, C., Schiex, T.: A comparative genome approach to marker ordering. Bioinformatics\u00a023(2), e50 (2007)","DOI":"10.1093\/bioinformatics\/btl321"},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/3-540-57273-2_52","volume-title":"Algorithms - ESA \u201993","author":"M. Fellows","year":"1993","unstructured":"Fellows, M., Hallett, M., Wareham, H.: DNA physical mapping: three ways of difficult. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol.\u00a0726, pp. 157\u2013168. Springer, Heidelberg (1993)"},{"key":"5_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/3-540-56686-4_38","volume-title":"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","author":"M. Fellows","year":"1993","unstructured":"Fellows, M., Hallett, M., Wareham, H.: Fixed-parameter complexity and cryptography. In: Moreno, O., Cohen, G., Mora, T. (eds.) AAECC 1993. LNCS, vol.\u00a0673, pp. 121\u2013131. Springer, Heidelberg (1993)"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Fellows, M., Langston, M.: On search, decision and the efficiency of polynomial-time algorithms. In: Proceedings of the 21st ACM Symposium on Theory of Computing (STOC), pp. 501\u2013512 (1989)","DOI":"10.1145\/73007.73055"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Fishburn, P.: Interval orders and interval graphs: A study of partially ordered sets. Wiley-Interscience Series in Discrete Mathematics, New York (1985)","DOI":"10.1016\/0012-365X(85)90042-1"},{"key":"5_CR18","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Springer-Verlag New York Inc. (2006)"},{"key":"5_CR19","first-page":"5","volume":"17","author":"H. Jiang","year":"2010","unstructured":"Jiang, H., Zhu, B.: Weak Kernels. Electronic Colloquium on Computational Complexity (ECCC)\u00a017, 5 (2010)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"880","DOI":"10.1137\/S0097539796303044","volume":"28","author":"H. Kaplan","year":"1999","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.: Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM Journal on Computing\u00a028, 880\u2013892 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"5_CR21","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford University Press, USA (2006)"},{"key":"5_CR22","unstructured":"Rafiey, A.: Single Exponential FPT Algorithm for Interval Vertex Deletion and Interval Completion Problem, http:\/\/arxiv.org\/pdf\/1211.4629v1.pdf"},{"issue":"6","key":"5_CR23","first-page":"1189","volume":"49","author":"C. Richard","year":"1991","unstructured":"Richard, C., Withers, D., Meeker, T., Maurer, S., Evans, G., Myers, R., Cox, D.: A radiation hybrid map of the proximal long arm of human chromosome 11 containing the multiple endocrine neoplasia type 1 (MEN-1) and bcl-1 disease loci. American Journal of Human Genetics\u00a049(6), 1189 (1991)","journal-title":"American Journal of Human Genetics"},{"issue":"4","key":"5_CR24","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1089\/cmb.1997.4.487","volume":"4","author":"D. Slonim","year":"1997","unstructured":"Slonim, D., Kruglyak, L., Stein, L., Lander, E.: Building human genome maps with radiation hybrids. Journal of Computational Biology\u00a04(4), 487\u2013504 (1997)","journal-title":"Journal of Computational Biology"},{"key":"5_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-642-31770-5_12","volume-title":"Combinatorial Optimization and Applications","author":"C. Zhang","year":"2012","unstructured":"Zhang, C., Jiang, H., Zhu, B.: Radiation hybrid map construction problem parameterized. In: Lin, G. (ed.) COCOA 2012. LNCS, vol.\u00a07402, pp. 127\u2013137. Springer, Heidelberg (2012)"},{"key":"5_CR26","unstructured":"West, D.: Introduction to graph theory. Prentice Hall Inc., Upper Saddle River (2006)"}],"container-title":["Lecture Notes in Computer Science","Bioinformatics Research and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38036-5_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T09:48:24Z","timestamp":1746006504000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38036-5_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642380358","9783642380365"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38036-5_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}