Departments  

Book Series (82) 
1138

Medienwissenschaften 
15

Humanities 
2088

Natural Sciences 
5194

Mathematics  221 
Informatics  301 
Physics  968 
Chemistry  1313 
Geosciences  125 
Human medicine  232 
Stomatology  10 
Veterinary medicine  88 
Pharmacy  144 
Biology  794 
Biochemistry, molecular biology, gene technology  108 
Biophysics  24 
Domestic and nutritional science  43 
Agricultural science  971 
Forest science  198 
Horticultural science  16 
Environmental research, ecology and landscape conservation  137 
Geographie 
1

Engineering 
1612

Common 
83

Leitlinien Unfallchirurgie
5. Auflage bestellen 
Table of Contents, Datei (54 KB)
Extract, Datei (200 KB)
ISBN13 (Printausgabe)  3867279438 
ISBN13 (Hard Copy)  9783867279437 
Language  English 
Page Number  206 
Edition  1 Aufl. 
Volume  0 
Publication Place  Göttingen 
Place of Dissertation  Universität Jena 
Publication Date  20090414 
General Categorization  Dissertation 
Departments 
Mathematics
Informatics 
This thesis is about the computational complexity of several combinatorial problems closely related to the consecutiveones property of binary matrices (0/1matrices). Herein, a binary matrix has the consecutiveones property (C1P) if there is a permutation of its columns that places the 1s consecutively in every row. The C1P has a long history and plays an important role in many applications, ranging from computational biology to railway optimization. This thesis aims, on the one hand, to investigate how the C1P can be established when a given binary matrix initially does not have this property, and, on the other hand, to analyze how the C1P and “relaxed” variants of the C1P can help to tackle matrix problems that are hard to solve in general. Apart from giving an overview on the C1P and its connections to graph theory and algorithmics, the thesis examines four problem complexes.
Finding small forbidden submatrices.
Here, one has given a binary matrix M without the C1P, and the task is to find a minimumsize submatrix of M that does not have the C1P. Such a submatrix is called a forbidden submatrix because it is a cause for the absence of the C1P in M. We show that a forbidden submatrix consisting of a minimum number of rows and columns can be found in polynomial time.
Obtaining the C1P by row or column deletions.
The problems of deleting a minimum number of rows or columns to transform a given matrix into a matrix with the C1P are called MinCOSR and MinCOSC, respectively. Both problems are known to be NPhard even on very sparse matrices, containing only two 1entries per row and at most three 1entries per column. Our main results for these problems and their maximization versions are approximation and fixedparameter algorithms for matrices that have only a bounded number of 1entries per row.
Covering problems on input matrices with the C1P.
Here, we consider two variants of the subset selection problem Set Cover. Both of these two problems can be modelled as matrix problems and are NPhard on general binary matrices; we investigate if they become polynomialtime solvable when some or all rows in the input matrix contain only one block of 1s each.
Rectangle stabbing in d dimensions.
(2Dimensional) Rectangle Stabbing is a geometric problem where the input consists of a set of axisparallel rectangles and a set of axisparallel lines, and the task is to select a minimum number of the given lines to intersect every rectangle at least once. The generalization of this problem to d dimensions is called dDimensional Rectangle Stabbing. We show that for every d>=2 dDimensional Rectangle Stabbing is W^{1}hard for the parameter “number of selected lines”. This result is complemented by fixedparameter algorithms for several restrictions of (2Dimensional) Rectangle Stabbing.
Parts of the thesis have already been published in the journal “Journal of Discrete Algorithms” and in the proceedings of the conferences “4th Annual Conference on Theory and Applications of Models of Computation (TAMC ’07)”, “3rd Algorithms and Complexity in Durham (ACiD ’07) Workshop”, “2nd International Frontiers of Algorithmics Workshop (FAW ’08)”, and “3rd International Workshop on Algorithms and Computation (WALCOM ’09)”.