{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:50:47Z","timestamp":1759063847178},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230717"},{"type":"electronic","value":"9783540286394"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-28639-4_1","type":"book-chapter","created":{"date-parts":[[2010,9,20]],"date-time":"2010-09-20T16:25:35Z","timestamp":1284999935000},"page":"1-12","source":"Crossref","is-referenced-by-count":13,"title":["Parameterized Enumeration, Transversals, and Imperfect Phylogeny Reconstruction"],"prefix":"10.1007","author":[{"given":"Peter","family":"Damaschke","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1137\/S0097539793244587","volume":"23","author":"R. Agarwala","year":"1994","unstructured":"Agarwala, R., Fern\u00e1ndez-Baca, D.: A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed. SIAM J. Computing\u00a023, 1216\u20131224 (1994)","journal-title":"SIAM J. Computing"},{"key":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/3-540-55719-9_80","volume-title":"Automata, Languages and Programming","author":"H. Bodlaender","year":"1992","unstructured":"Bodlaender, H., Fellows, M., Warnow, T.: Two strikes against perfect phylogeny. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.\u00a0623, pp. 273\u2013283. Springer, Heidelberg (1992)"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L.: Generating dual-bounded hypergraphs, DIMACS Tech. Report 2002-23","DOI":"10.1080\/1055678021000060801"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J.F. Buss","year":"1993","unstructured":"Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM J. on Computing\u00a022, 560\u2013572 (1993)","journal-title":"SIAM J. on Computing"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. of Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"J. of Algorithms"},{"key":"1_CR6","unstructured":"Damaschke, P.: Incremental haplotype inference, phylogeny and almost bipartite graphs. In: 2nd RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotypes 2004, pre-proceedings, Carnegie Mellon Univ., pp. 1\u201311 (2004)"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Downey, R.G.: Parameterized complexity for the skeptic. In: 18th IEEE Conf. on Computational Complexity, pp. 147\u2013170 (2003)","DOI":"10.1109\/CCC.2003.1214417"},{"key":"1_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"1_CR9","series-title":"AMSDIMACS Series","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1090\/dimacs\/049\/04","volume-title":"Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Futur","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R., Stege, U.: Parameterized complexity, a framework for systematically confronting computational intractability. In: Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Futur. AMSDIMACS Series, vol.\u00a049, pp. 49\u201399. Springer, Heidelberg (1999)"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Fern\u00e1ndez-Baca, D., Lagergren, J.: A polynomial-time algorithm for near-perfect phylogeny. In: To appear in SIAM J. Computing, preliminary version in 23rd ICALP 1996 (1996)","DOI":"10.1007\/3-540-61440-0_168"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1007\/3-540-45655-4_60","volume-title":"Computing and Combinatorics","author":"H. Fernau","year":"2002","unstructured":"Fernau, H.: On parameterized enumeration. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol.\u00a02387, pp. 564\u2013573. Springer, Heidelberg (2002)"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1006\/jagm.1996.0062","volume":"21","author":"M.L. Freidman","year":"1996","unstructured":"Freidman, M.L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. J. of Algorithms\u00a021, 618\u2013628 (1996)","journal-title":"J. of Algorithms"},{"key":"1_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/3-540-48194-X_23","volume-title":"Combinatorial Pattern Matching","author":"J. Gramm","year":"2001","unstructured":"Gramm, J., Niedermeier, R.: Quartet inconsistency is fixed-parameter tractable. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 241\u2013256. Springer, Heidelberg (2001)"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Gramm, J., Niedermeier, R.: Breakpoint medians and breakpoint phylogenies: a fixed-parameter approach. In: 1st Europ. Conf. on Comput. Biology 2002, Supplement 2 to Bioinformatics, vol.\u00a018, pp. 128\u2013139 (2002)","DOI":"10.1093\/bioinformatics\/18.suppl_2.S128"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D. Gusfield","year":"1991","unstructured":"Gusfield, D.: Efficient algorithms for inferring evolutionary trees. Networks\u00a021, 19\u201328 (1991)","journal-title":"Networks"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Halperin, E., Karp, R.M.: Perfect phylogeny and haplotype inference. In: 8th RECOMB 2004, pp. 10\u201319 (2004)","DOI":"10.1145\/974614.974617"},{"key":"1_CR17","unstructured":"Jansson, J.: Consensus algorithms for trees and strings, Dissertation 17, Dept. of Computer Science, Lund Univ. (2003)"},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Info. Proc. Letters\u00a027, 119\u2013123 (1988)","journal-title":"Info. Proc. Letters"},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"1749","DOI":"10.1137\/S0097539794279067","volume":"26","author":"S. Kannan","year":"1997","unstructured":"Kannan, S., Warnow, T.: A fast algorithm for the computation and enumeration of perfect phylogenies. SIAM J. Computing\u00a026, 1749\u20131763 (1997)","journal-title":"SIAM J. Computing"},{"key":"1_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/3-540-48318-7_8","volume-title":"Algorithm Engineering","author":"D.J. Kavvadias","year":"1999","unstructured":"Kavvadias, D.J., Stavropoulos, E.C.: A new algorithm for the transversal hypergraph problem. In: Vitter, J.S., Zaroliagis, C.D. (eds.) WAE 1999. LNCS, vol.\u00a01668, pp. 72\u201384. Springer, Heidelberg (1999)"},{"key":"1_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"STACS 99","author":"R. Niedermeier","year":"1999","unstructured":"Niedermeier, R., Rossmanith, P.: Upper bounds for vertex cover further improved. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 561\u2013570. Springer, Heidelberg (1999)"},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S1570-8667(03)00009-1","volume":"1","author":"R. Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: An efficient fixed parameter algorithm for 3-Hitting Set. J. of Discrete Algorithms\u00a01, 89\u2013102 (2003)","journal-title":"J. of Discrete Algorithms"},{"key":"1_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/3-540-45123-4_14","volume-title":"Combinatorial Pattern Matching","author":"I. Pe\u2019er","year":"2000","unstructured":"Pe\u2019er, I., Shamir, R., Sharan, R.: Incomplete directed perfect phylogeny. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol.\u00a01848, pp. 143\u2013153. Springer, Heidelberg (2000)"},{"key":"1_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/3-540-45471-3_37","volume-title":"Algorithm Theory - SWAT 2002","author":"I. Pe\u2019er","year":"2002","unstructured":"Pe\u2019er, I., Shamir, R., Sharan, R.: On the generality of phylogenies from incomplete directed characters. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol.\u00a02368, pp. 358\u2013367. Springer, Heidelberg (2002)"},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M.A. Steel","year":"1992","unstructured":"Steel, M.A.: The complexity of reconstructing trees from qualitative characters and subtrees. J. of Classification\u00a09, 91\u2013116 (1992)","journal-title":"J. of Classification"},{"key":"1_CR26","unstructured":"Warnow, T., Ringe, D., Taylor, A.: Reconstructing the evolutionary history of natural languages. In: 7th SODA 1996, pp. 314\u2013322 (1996)"},{"key":"1_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-6846-3","volume-title":"Introduction to Computational Biology","author":"M.S. Waterman","year":"1995","unstructured":"Waterman, M.S.: Introduction to Computational Biology. Chapman and Hall, Boca Raton (1995)"},{"key":"1_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/978-3-540-24618-3_30","volume-title":"SOFSEM 2004: Theory and Practice of Computer Science","author":"S. Wernicke","year":"2004","unstructured":"Wernicke, S., Alber, J., Gramm, J., Guo, J., Niedermeier, R.: Avoiding forbidden submatrices by row deletions. In: Van Emde Boas, P., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2004. LNCS, vol.\u00a02932, pp. 349\u2013360. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-28639-4_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:26:44Z","timestamp":1605742004000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-28639-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230717","9783540286394"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-28639-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}