{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T05:34:10Z","timestamp":1771911250592,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,9,22]],"date-time":"2007-09-22T00:00:00Z","timestamp":1190419200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s00453-007-9008-7","type":"journal-article","created":{"date-parts":[[2007,9,21]],"date-time":"2007-09-21T15:34:29Z","timestamp":1190388869000},"page":"114-132","source":"Crossref","is-referenced-by-count":48,"title":["Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection"],"prefix":"10.1007","volume":"52","author":[{"given":"Falk","family":"H\u00fcffner","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Wernicke","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Zichner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,9,22]]},"reference":[{"issue":"4","key":"9008_CR1","first-page":"844","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J.\u00a0ACM 42(4), 844\u2013856 (1995)","journal-title":"J.\u00a0ACM"},{"key":"9008_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: On linear time minor tests with depth-first search. J.\u00a0Algorithms 14(1) (1993)","DOI":"10.1006\/jagm.1993.1001"},{"key":"9008_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/11847250_22","volume-title":"Proc. 2nd Int. Workshop on Parameterized and Exact Computation (IWPEC\u201906)","author":"L. Cai","year":"2006","unstructured":"Cai, L., Chan, S.M., Chan, S.O.: Random separation: a new method for solving fixed-cardinality optimization problems. In: Proc. 2nd Int. Workshop on Parameterized and Exact Computation (IWPEC\u201906). Lecture Notes in Computer Science, vol.\u00a04169, pp.\u00a0239\u2013250. Springer, New York (2006)"},{"key":"9008_CR4","unstructured":"Cappanera, P., Scutell\u00e0, M.G.: Balanced paths in telecommunication networks: some computational results. In: Proc. 3rd Int. Network Optimization Conference (INOC\u201907) (2007)"},{"key":"9008_CR5","unstructured":"Chen, J., Lu, S., Sze, S.-H., Zhang, F.: Improved algorithms for path, matching, and packing problems. In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907), pp.\u00a0298\u2013307. ACM-SIAM (2007)"},{"key":"9008_CR6","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"key":"9008_CR7","unstructured":"Deshpande, P., Barzilay, R., Karger, D.R.: Randomized decoding for selection-and-ordering problems. In: Proc. Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technologies (NAACL HLT\u201907), pp.\u00a0444\u2013451. Association for Computational Linguistics (2007)"},{"key":"9008_CR8","series-title":"Lecture Notes in Bioinformatics","first-page":"1","volume-title":"Proc. 11th Annual Int. Conference on Research in Computational Molecular Biology (RECOMB\u201907)","author":"B. Dost","year":"2007","unstructured":"Dost, B., Shlomi, T., Gupta, N., Ruppin, E., Bafna, V., Sharan, R.: QNet: a tool for querying protein interaction networks. In: Proc. 11th Annual Int. Conference on Research in Computational Molecular Biology (RECOMB\u201907). Lecture Notes in Bioinformatics, vol.\u00a04453, pp.\u00a01\u201315. Springer, New York (2007)"},{"key":"9008_CR9","first-page":"166","volume-title":"Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"T. Feder","year":"2005","unstructured":"Feder, T., Motwani, R.: Finding large cycles in Hamiltonian graphs. In: Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905), pp.\u00a0166\u2013175. SIAM, Philadelphia (2005)"},{"key":"9008_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/978-3-540-30140-0_29","volume-title":"Proc. 12th European Symposium on Algorithms (ESA\u201904)","author":"M.R. Fellows","year":"2004","unstructured":"Fellows, M.R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F.A., Stege, U., Thilikos, D.M., Whitesides, S.: Faster fixed-parameter tractable algorithms for matching and packing problems. In: Proc. 12th European Symposium on Algorithms (ESA\u201904). Lecture Notes in Computer Science, vol.\u00a03221, pp.\u00a0311\u2013322. Springer, New York (2004)"},{"key":"9008_CR11","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: Finding paths and cycles of superpolylogarithmic length. In: Proc. 36th ACM Symposium on Theory of Computing (STOC\u201904), pp.\u00a0407\u2013416. ACM (2004)","DOI":"10.1145\/1007352.1007418"},{"issue":"5651","key":"9008_CR12","doi-asserted-by":"crossref","first-page":"1727","DOI":"10.1126\/science.1090289","volume":"302","author":"L. Giot","year":"2003","unstructured":"Giot, L., Bader, J.S., Brouwer, C., et al.: A\u00a0protein interaction map of Drosophila melanogaster. Science 302(5651), 1727\u20131736 (2003)","journal-title":"Science"},{"issue":"1","key":"9008_CR13","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M. Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A\u00a0dynamic programming approach to sequencing problems. J.\u00a0Soc. Ind. Appl. Math. 10(1), 196\u2013210 (1962)","journal-title":"J.\u00a0Soc. Ind. Appl. Math."},{"issue":"13","key":"9008_CR14","doi-asserted-by":"crossref","first-page":"1708","DOI":"10.1093\/bioinformatics\/btm160","volume":"23","author":"F. H\u00fcffner","year":"2007","unstructured":"H\u00fcffner, F., Wernicke, S., Zichner, T.: FASPAD: fast signaling pathway detection. Bioinformatics 23(13), 1708\u20131709 (2007)","journal-title":"Bioinformatics"},{"issue":"5518","key":"9008_CR15","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1126\/science.292.5518.929","volume":"292","author":"T. Ideker","year":"2001","unstructured":"Ideker, T., Thorsson, V., Ranish, J.A., et al.: Integrated genomic and proteomic analyses of a systematically perturbed metabolic network. Science 292(5518), 929\u2013934 (2001)","journal-title":"Science"},{"issue":"1","key":"9008_CR16","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"D.R. Karger","year":"1997","unstructured":"Karger, D.R., Motwani, R., Ramkumar, G.D.S.: On approximating the longest path in a graph. Algorithmica 18(1), 82\u201398 (1997)","journal-title":"Algorithmica"},{"key":"9008_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1007\/11917496_6","volume-title":"Proc. 32nd Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201906)","author":"J. Kneis","year":"2006","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: Divide-and-color. In: Proc. 32nd Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201906). Lecture Notes in Computer Science, vol.\u00a04271, pp.\u00a058\u201367. Springer, New York (2006)"},{"issue":"1","key":"9008_CR18","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/j.ipl.2004.12.005","volume":"94","author":"I. Koutis","year":"2005","unstructured":"Koutis, I.: A faster parameterized algorithm for Set Packing. Inf. Process. Lett. 94(1), 7\u20139 (2005)","journal-title":"Inf. Process. Lett."},{"key":"9008_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/978-3-540-28639-4_12","volume-title":"Proc. 1st Int. Workshop on Parameterized and Exact Computation (IWPEC\u201904)","author":"L. Mathieson","year":"2004","unstructured":"Mathieson, L., Prieto, E., Shaw, P.: Packing edge disjoint triangles: a parameterized view. In: Proc. 1st Int. Workshop on Parameterized and Exact Computation (IWPEC\u201904). Lecture Notes in Computer Science, vol.\u00a03162, pp.\u00a0127\u2013137. Springer, New York (2004)"},{"issue":"1","key":"9008_CR20","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1093\/nar\/gkl975","volume":"35","author":"I. Mayrose","year":"2007","unstructured":"Mayrose, I., Shlomi, T., Rubinstein, N.D., Gershoni, J.M., Ruppin, E., Sharan, R., Pupko, T.: Epitope mapping using combinatorial phage-display libraries: a graph-based algorithm. Nucleic Acids Res. 35(1), 69\u201378 (2007)","journal-title":"Nucleic Acids Res."},{"key":"9008_CR21","first-page":"239","volume":"25","author":"B. Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. Ann. Discret. Math. 25, 239\u2013254 (1985)","journal-title":"Ann. Discret. Math."},{"key":"9008_CR22","doi-asserted-by":"crossref","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, Oxford (2006)"},{"key":"9008_CR23","series-title":"Lecture Notes in Computer Science","first-page":"18","volume-title":"Proc. 16th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201990)","author":"J. Plehn","year":"1990","unstructured":"Plehn, J., Voigt, B.: Finding minimally weighted subgraphs. In: Proc. 16th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201990). Lecture Notes in Computer Science, vol.\u00a0484, pp.\u00a018\u201329. Springer, New York (1990)"},{"issue":"3","key":"9008_CR24","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/j.tcs.2005.10.009","volume":"351","author":"E. Prieto","year":"2006","unstructured":"Prieto, E., Sloper, C.: Looking at the stars. Theor. Comput. Sci. 351(3), 437\u2013445 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9008_CR25","unstructured":"Raymann, D.: Implementation of Alon-Yuster-Zwick\u2019s color-coding algorithm. Diplomarbeit, Institute of Theoretical Computer Science, ETH Z\u00fcrich, Switzerland (2004)"},{"issue":"5","key":"9008_CR26","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"J.P. Schmidt","year":"1990","unstructured":"Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput. 19(5), 775\u2013786 (1990)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9008_CR27","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1089\/cmb.2006.13.133","volume":"13","author":"J. Scott","year":"2006","unstructured":"Scott, J., Ideker, T., Karp, R.M., Sharan, R.: Efficient algorithms for detecting signaling pathways in protein interaction networks. J.\u00a0Comput. Biol. 13(2), 133\u2013144 (2006)","journal-title":"J.\u00a0Comput. Biol."},{"issue":"4","key":"9008_CR28","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1038\/nbt1196","volume":"24","author":"R. Sharan","year":"2006","unstructured":"Sharan, R., Ideker, T.: Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24(4), 427\u2013433 (2006)","journal-title":"Nat. Biotechnol."},{"key":"9008_CR29","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1186\/1471-2105-7-199","volume":"7","author":"T. Shlomi","year":"2006","unstructured":"Shlomi, T., Segal, D., Ruppin, E., Sharan, R.: QPath: a method for querying pathways in a protein\u2013protein interaction network. BMC Bioinf. 7, 199 (2006)","journal-title":"BMC Bioinf."},{"key":"9008_CR30","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1186\/1471-2105-3-34","volume":"3","author":"M. Steffen","year":"2002","unstructured":"Steffen, M., Petti, A., Aach, J., D\u2019haeseleer, P., Church, G.: Automated modelling of signal transduction networks. BMC Bioinf. 3, 34 (2002)","journal-title":"BMC Bioinf."},{"key":"9008_CR31","doi-asserted-by":"crossref","first-page":"056115","DOI":"10.1103\/PhysRevE.70.056115","volume":"70","author":"E. Volz","year":"2004","unstructured":"Volz, E.: Random networks with tunable degree distribution and clustering. Phys. Rev. E 70, 056115 (2004)","journal-title":"Phys. Rev. E"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9008-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9008-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9008-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:44:59Z","timestamp":1559123099000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9008-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,22]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["9008"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9008-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,22]]}}}