{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:16Z","timestamp":1740109276499,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,5,15]],"date-time":"2018-05-15T00:00:00Z","timestamp":1526342400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P25518-N23","P26696"],"award-info":[{"award-number":["P25518-N23","P26696"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["ER 738\/2-1"],"award-info":[{"award-number":["ER 738\/2-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,1]]},"DOI":"10.1007\/s00453-018-0442-5","type":"journal-article","created":{"date-parts":[[2018,5,15]],"date-time":"2018-05-15T08:11:42Z","timestamp":1526371902000},"page":"201-223","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity of Asynchronous Border Minimization"],"prefix":"10.1007","volume":"81","author":[{"given":"Robert","family":"Ganian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Kronegger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Pfandler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandru","family":"Popa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,5,15]]},"reference":[{"issue":"6","key":"442_CR1","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/s00224-006-1350-7","volume":"39","author":"K Andreev","year":"2006","unstructured":"Andreev, K., R\u00e4cke, H.: Balanced graph partitioning. Theory Comput. Syst. 39(6), 929\u2013939 (2006)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"442_CR2","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1158\/0008-5472.CAN-04-2962","volume":"66","author":"M Chatterjee","year":"2006","unstructured":"Chatterjee, M., Mohapatra, S., Ionan, A., Bawa, G., Ali-Fehmi, R., Wang, X., Nowak, J., Ye, B., Nahhas, F.A., Lu, K., Witkin, S.S., Fishman, D., Munkarah, A., Morris, R., Levin, N.K., Shirley, N.N., Tromp, G., Abrams, J., Draghici, S., Tainsky, M.A.: Diagnostic markers of ovarian cancer by high-throughput antigen cloning and detection on arrays. Cancer Res. 66(2), 1181\u20131190 (2006)","journal-title":"Cancer Res."},{"key":"442_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-60327-394-7","volume-title":"Peptide Microarrays: Methods and Protocols. Methods in Molecular Biology","author":"M Cretich","year":"2009","unstructured":"Cretich, M., Chiari, M.: Peptide Microarrays: Methods and Protocols. Methods in Molecular Biology. Humana Press, New York (2009)"},{"key":"442_CR4","doi-asserted-by":"crossref","unstructured":"de Carvalho Jr., S.A., Rahmann, S.: Improving the layout of oligonucleotide microarrays: pivot partitioning. In: Proceedings of WABI. Lecture Notes in Computer Science, vol. 4175, pp. 321\u2013332. Springer (2006)","DOI":"10.1007\/11851561_30"},{"key":"442_CR5","unstructured":"de Carvalho Jr., S.A., Rahmann, S.: Microarray layout as quadratic assignment problem. In: Proceedings of GCB. Lecture Notes in Informatics, vol. 83, pp. 11\u201320. GI (2006)"},{"key":"442_CR6","doi-asserted-by":"crossref","unstructured":"de Carvalho Jr., S.A., Rahmann, S.: Improving the design of genechip arrays by combining placement and embedding. In: Proceedings of CSB, vol. 6, pp. 54\u201363. Imperial College Press (2007)","DOI":"10.1142\/9781860948732_0042"},{"key":"442_CR7","unstructured":"de Carvalho Jr., S.A., Rahmann, S.: Microarray design and layout. \n                    http:\/\/genomeinformatics.uni-due.de\/research\/microarray-design-and-layout\/\n                    \n                  . Accessed 21 Feb 2017"},{"key":"442_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity. Monographs in Computer Science","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Berlin (1999)"},{"key":"442_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"key":"442_CR10","unstructured":"Feldmann, A.E.: Balanced partitions of grids and related graphs. Ph.D. thesis, ETH Z\u00fcrich (2012)"},{"key":"442_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2013.03.014","volume":"485","author":"AE Feldmann","year":"2013","unstructured":"Feldmann, A.E.: Fast balanced partitioning is hard even on grids and trees. Theor. Comput. Sci. 485, 61\u201368 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"442_CR12","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Proceedings of ISAAC. Lecture Notes in Computer Science, vol. 5369, pp. 294\u2013305. Springer (2008)","DOI":"10.1007\/978-3-540-92182-0_28"},{"issue":"2","key":"442_CR13","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0890-5401(03)00161-5","volume":"187","author":"J Flum","year":"2003","unstructured":"Flum, J., Grohe, M.: Describing parameterized complexity classes. Inf. Comput. 187(2), 291\u2013319 (2003)","journal-title":"Inf. Comput."},{"key":"442_CR14","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"issue":"4995","key":"442_CR15","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1126\/science.1990438","volume":"251","author":"S Fodor","year":"1991","unstructured":"Fodor, S., Read, J.L., Pirrung, M.C., Stryer, L., Lu, A.T., Solas, D.: Light-directed, spatially addressable parallel chemical synthesis. Science 251(4995), 767\u2013773 (1991)","journal-title":"Science"},{"issue":"1","key":"442_CR16","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49\u201365 (1987)","journal-title":"Combinatorica"},{"key":"442_CR17","doi-asserted-by":"crossref","unstructured":"Ganian, R., Kronegger, M., Pfandler, A., Popa, A.: Parameterized complexity of asynchronous border minimization. In: Proceedings of TAMC. Lecture Notes in Computer Science, vol. 9076, pp. 428\u2013440. Springer (2015)","DOI":"10.1007\/978-3-319-17142-5_36"},{"issue":"5","key":"442_CR18","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/S0968-0004(99)01382-1","volume":"24","author":"D Gerhold","year":"1999","unstructured":"Gerhold, D., Rushmore, T., Caskey, C.T.: DNA chips: promising toys have become powerful tools. Trends Biochem. Sci. 24(5), 168\u2013173 (1999)","journal-title":"Trends Biochem. Sci."},{"key":"442_CR19","first-page":"1","volume":"77","author":"S Hannenhalli","year":"2002","unstructured":"Hannenhalli, S., Hubell, E., Lipshutz, R., Pevzner, P.A.: Combinatorial algorithms for design of DNA arrays. Adv. Biochem. Eng. Biotechnol. 77, 1\u201319 (2002)","journal-title":"Adv. Biochem. Eng. Biotechnol."},{"key":"442_CR20","doi-asserted-by":"crossref","unstructured":"Kahng, A.B., Mandoiu, I.I., Pevzner, P.A., Reda, S., Zelikovsky, A.: Scalable heuristics for design of DNA probe arrays. J. Comput. Biol. 11(2\/3), 429\u2013447 (2004). Preliminary versions in WABI (2002) and RECOMB (2003)","DOI":"10.1089\/1066527041410391"},{"issue":"2","key":"442_CR21","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1109\/TCAD.2005.855940","volume":"25","author":"AB Kahng","year":"2006","unstructured":"Kahng, A.B., Mandoiu, I.I., Reda, S., Xu, X., Zelikovsky, A.: Computer-aided optimization of DNA array design and manufacturing. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 25(2), 305\u2013320 (2006)","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"issue":"3","key":"442_CR22","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"key":"442_CR23","doi-asserted-by":"crossref","unstructured":"Kundeti, V., Rajasekaran, S.: On the hardness of the border length minimization problem. In: Proceedings of BIBE, pp. 248\u2013253. IEEE Computer Society (2009)","DOI":"10.1109\/BIBE.2009.26"},{"issue":"6","key":"442_CR24","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1089\/cmb.2013.0127","volume":"21","author":"V Kundeti","year":"2014","unstructured":"Kundeti, V., Rajasekaran, S., Dinh, H.: Border length minimization problem on a square array. J. Comput. Biol. 21(6), 446\u2013455 (2014)","journal-title":"J. Comput. Biol."},{"key":"442_CR25","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H Lenstra","year":"1983","unstructured":"Lenstra, H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"442_CR26","doi-asserted-by":"crossref","unstructured":"Li, C.Y., Wong, P.W.H., Xin, Q., Yung, F.C.C.: Approximating border length for DNA microarray synthesis. In: Proceedings of TAMC. Lecture Notes in Computer Science, vol. 4978, pp. 410\u2013422. Springer (2008)","DOI":"10.1007\/978-3-540-79228-4_36"},{"issue":"12","key":"442_CR27","doi-asserted-by":"publisher","first-page":"4099","DOI":"10.1158\/0008-5472.CAN-03-3807","volume":"64","author":"C Melle","year":"2004","unstructured":"Melle, C., Ernst, G., Schimmel, B., Bleul, A., Koscielny, S., Wiesner, A., Bogumil, R., M\u00f6ller, U., Osterloh, D., Halbhuber, K.-J., von Eggeling, F.: A technical triade for proteomic identification and characterization of cancer biomarkers. Cancer Res. 64(12), 4099\u20134104 (2004)","journal-title":"Cancer Res."},{"key":"442_CR28","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"442_CR29","doi-asserted-by":"crossref","unstructured":"Popa, A., Wong, P.W.H., Yung, F.C.C.: Hardness and approximation of the asynchronous border minimization problem (extended abstract). In: Proceedings of TAMC. Lecture Notes in Computer Science, vol. 7287, pp. 164\u2013176. Springer (2012)","DOI":"10.1007\/978-3-642-29952-0_20"},{"key":"442_CR30","doi-asserted-by":"crossref","unstructured":"Slonim, D.K., Tamayo, P., Mesirov, J.P., Golub, T.R., Lander, E.S.: Class prediction and discovery using gene expression data. In: Proceedings of RECOMB, pp. 263\u2013272. ACM (2000)","DOI":"10.1145\/332306.332564"},{"issue":"6","key":"442_CR31","doi-asserted-by":"publisher","first-page":"3410","DOI":"10.1073\/pnas.0530278100","volume":"100","author":"JB Welsh","year":"2003","unstructured":"Welsh, J.B., Sapinoso, L.M., Kern, S.G., Brown, D.A., Liu, T., Bauskin, A.R., Ward, R.L., Hawkins, N.J., Quinn, D.I., Russell, P.J., Sutherland, R.L., Breit, S.N., Moskaluk, C.A., Frierson Jr., H.F., Hampton, G.M.: Large-scale delineation of secreted protein biomarkers overexpressed in cancer tissue and serum. Proc. Natl. Acad. Sci. 100(6), 3410\u20133415 (2003)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"15","key":"442_CR32","doi-asserted-by":"publisher","first-page":"4952","DOI":"10.1093\/nar\/gkm514","volume":"35","author":"Y Zhang","year":"2007","unstructured":"Zhang, Y., Gladyshev, V.N.: High content of proteins containing 21st and 22nd amino acids, selenocysteine and pyrrolysine, in a symbiotic deltaproteobacterium of gutless worm olavius algarvensis. Nucleic Acids Res. 35(15), 4952\u20134963 (2007)","journal-title":"Nucleic Acids Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0442-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0442-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0442-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T20:12:04Z","timestamp":1557864724000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0442-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,15]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["442"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0442-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,5,15]]},"assertion":[{"value":"27 August 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 April 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}