[Back]

R. Ganian, M. Kronegger, A. Pfandler, A. Popa:
"Parameterized Complexity of Asynchronous Border Minimization";
Talk: 12th Annual Conference on Theory and Applications of Models of Computation, TAMC 2015, Singapur; 2015-05-18 - 2015-05-20; in: "Theory and Applications of Models of Computation, 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings", R. Jain, S. Jain, F. Stephan (ed.); Springer, Lecture Notes in Computer Science Volume 9076 (2015), ISBN: 978-3-319-17141-8; 428 - 440.

Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). In this paper we investigate the parameterized complexity of natural variants of BMP and P-BMP, termed BMP^e and P-BMP^e respectively, under several natural parameters. We show that BMP^e and P-BMP^e are in FPT under the following two combinations of parameters: (1) the size of the alphabet (c), the maximum length of a sequence (string) in the input (ℓ) and the number of rows of the microarray (r); and, (2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMP^e is in FPT when parameterized by c and ℓ. We complement our tractability results with corresponding hardness results.

http://dx.doi.org/10.1007/978-3-319-17142-5_36

Project Head Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen