{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T10:46:47Z","timestamp":1649069207693},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,3,10]],"date-time":"2015-03-10T00:00:00Z","timestamp":1425945600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1007\/s00453-015-9980-2","type":"journal-article","created":{"date-parts":[[2015,3,9]],"date-time":"2015-03-09T14:19:53Z","timestamp":1425910793000},"page":"992-1018","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Ordered List Subgraph Embedding Problems"],"prefix":"10.1007","volume":"74","author":[{"given":"Olawale","family":"Hassan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iyad","family":"Kanj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ljubomir","family":"Perkovi\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,3,10]]},"reference":[{"issue":"2\u20133","key":"9980_CR1","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.tcs.2003.10.026","volume":"312","author":"J Alber","year":"2004","unstructured":"Alber, J., Gramm, J., Guo, J., Niedermeier, R.: Computing the similarity of two sequences with nested arc annotations. Theoret. Comput. Sci. 312(2\u20133), 337\u2013358 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"9980_CR2","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42, 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"9980_CR3","doi-asserted-by":"crossref","unstructured":"Ashby, C., Huang, X., Johnson, D., Kanj, I., Walker, K., Xia, G.: New algorithm for protein structure comparison and classification. BMC Genomics. 14, S2:S1 (2012)","DOI":"10.1186\/1471-2164-14-S2-S1"},{"key":"9980_CR4","doi-asserted-by":"crossref","unstructured":"Cai, L., Chan, S.-M., Chan, S.-O.: Random separation: a new method for solving fixed-cardinality optimization problems. In: Proceedings of the Second International Workshop on Parameterized and Exact Computation, Volume 4169 of Lecture Notes in Computer Science, pp. 239\u2013250. Springer, New York (2006)","DOI":"10.1007\/11847250_22"},{"issue":"40\u201342","key":"9980_CR5","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I., Xia, G.: Improved upper bounds for vertex cover. Theoret. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theoret. Comput. Sci."},{"key":"9980_CR6","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"R Downey","year":"1995","unstructured":"Downey, R., Fellows, M.: Parameterized computational feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, pp. 219\u2013244. Birkhauser, Boston (1995)"},{"key":"9980_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"R Downey","year":"2013","unstructured":"Downey, R., Fellows, M.: Fundamentals of Parameterized Complexity. Springer, New York (2013)"},{"key":"9980_CR8","unstructured":"Evans, P.: Algorithms and complexity for annotated sequence analysis. Technical report, Ph.D. thesis, University of Victoria (1999)"},{"key":"9980_CR9","doi-asserted-by":"crossref","unstructured":"Evans, P.: Finding common subsequences with arcs and pseudoknots. In: Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, Volume 1645 of Lecture Notes in Computer Science, pp. 270\u2013280. Springer, New York (1999)","DOI":"10.1007\/3-540-48452-3_20"},{"issue":"2","key":"9980_CR10","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/j.jda.2007.06.002","volume":"6","author":"I Fagnot","year":"2008","unstructured":"Fagnot, I., Lelandais, G., Vialette, S.: Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs. J. Discrete Algorithms 6(2), 178\u2013191 (2008)","journal-title":"J. Discrete Algorithms"},{"key":"9980_CR11","doi-asserted-by":"crossref","unstructured":"G. Fertin, R. Rizzi, S. Vialette: Finding exact and maximum occurrences of protein complexes in protein-protein interaction graphs. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, Volume 3618 of Lecture Notes in Computer Science, pp. 328\u2013339. Springer, New York (2005)","DOI":"10.1007\/11549345_29"},{"issue":"1","key":"9980_CR12","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.jda.2008.11.003","volume":"7","author":"G Fertin","year":"2009","unstructured":"Fertin, G., Rizzi, R., Vialette, S.: Finding occurrences of protein complexes in protein-protein interaction graphs. J. Discrete Algorithms 7(1), 90\u2013101 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"9980_CR13","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2010","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2010)"},{"key":"9980_CR14","doi-asserted-by":"crossref","unstructured":"Goldman, D., Istrail, S., Papadimitriou, C.: Algorithmic aspects of protein structure similarity. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pp. 512\u2013522 (1999)","DOI":"10.1109\/SFFCS.1999.814624"},{"key":"9980_CR15","doi-asserted-by":"crossref","unstructured":"Gramm, J., Guo, J., Niedermeier, R.: On exact and approximation algorithms for distinguishing substring selection. In: Proceedings of the 4th International Symposium on Fundamentals of Computation Theory, Volume 2751 of Lecture Notes in Computer Science, pp. 195\u2013209 (2003)","DOI":"10.1007\/978-3-540-45077-1_19"},{"issue":"4","key":"9980_CR16","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/s00224-004-1185-z","volume":"39","author":"J Gramm","year":"2006","unstructured":"Gramm, J., Guo, J., Niedermeier, R.: Parameterized intractability of distinguishing substring selection. Theory Comput. Syst. 39(4), 545\u2013560 (2006)","journal-title":"Theory Comput. Syst."},{"key":"9980_CR17","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.tcs.2012.12.049","volume":"494","author":"S Hartung","year":"2013","unstructured":"Hartung, S., Niedermeier, R.: Incremental list coloring of graphs, parameterized by conservation. Theoret. Comput. Sci. 494, 86\u201398 (2013)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"9980_CR18","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S1570-8667(03)00080-7","volume":"2","author":"T Jiang","year":"2004","unstructured":"Jiang, T., Lin, G., Ma, B., Zhang, K.: The longest common subsequence problem for arc-annotated sequences. J. Discrete Algorithms 2(2), 257\u2013270 (2004)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"9980_CR19","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0020-0190(90)90180-6","volume":"36","author":"H Kim","year":"1990","unstructured":"Kim, H.: Finding a maximum independent set in a permutation graph. Inf. Process. Lett. 36(1), 19\u201323 (1990)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9980_CR20","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1016\/S0022-0000(02)00004-1","volume":"65","author":"G-H Lin","year":"2002","unstructured":"Lin, G.-H., Chen, Z.-Z., Jiang, T., Wen, J.: The longest common subsequence problem for sequences with nested arc annotations. J. Comput. Syst. Sci. 65(3), 465\u2013480 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"9980_CR21","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pp. 182\u2013191 (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"key":"9980_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":"9980_CR23","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43, 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9980_CR24","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1109\/TCBB.2006.52","volume":"3","author":"Y Song","year":"2006","unstructured":"Song, Y., Liu, C., Huang, X., Malmberg, R., Xu, Y., Cai, L.: Efficient parameterized algorithms for biopolymer structure-sequence alignment. IEEE\/ACM Trans. Comput. Biol. Bioinf. 3(4), 423\u2013432 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"9980_CR25","volume-title":"Introduction to Graph Theory","author":"D West","year":"1996","unstructured":"West, D.: Introduction to Graph Theory. Prentice Hall Inc, New Jersey (1996)"},{"key":"9980_CR26","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 681\u2013690 (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9980-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9980-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9980-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T16:04:01Z","timestamp":1566403441000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9980-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,10]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["9980"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9980-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,10]]}}}