Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 8 of 8 for “"parameterized complexity"”.
-
Model-checking problems, machines and parameterized complexity
Parameterized complexity is a new approach to deal with classical <br>intractable problem. It is built on a novel notion of <br>tractability, i.e., fixed-parameter tractability, which <br>admits algorithms that have exponential running time, but <br>just in terms of parameter of the problem …
-
The Parameterized Complexity of Degree Constrained Editing Problems
… editing problems within the framework of parameterized complexity. A degree constrained editing problem takes as input a graph and a set of constraints and asks whether the graph can be altered in at most k editing steps such that the degrees of the remaining vertices are within the given …
-
Easy instances for model checking
Our interest is focused on the complexity of the model-checking problem and its generalizations. This question is intimately related to the expressibility of the logical language in question. We investigate the parameterized complexity of queries expressible in monadic second order logic over …
-
Intuitive algorithms
… of moderately exponential time algorithms and parameterized complexity provide tools for solving many of these problems in reasonable time. In this thesis, we introduce the concept of intuitive algorithms. While intuitive algorithms can be either moderately exponential time algorithms or …
-
Finding Interesting Subgraphs with Guarantees
… with guarantees by adapting techniques from parameterized complexity, convex optimization, and submodularity optimization. These techniques are well-known in the algorithm design literature, but they lead to slow and impractical algorithms. One unifying theme in the problems that we study is …
-
Exact algorithms based on specific complexity measures for hard problems
… polynomial-time transformations. A typical time complexity for this case is O(c^n) with c > 1.1.Under the widely accepted assumption that P does not equal NP, exact algorithms for problems of the second variety inevitably take superpolynomial time (not necessarily for every input, but in the …
-
Free-boundary problem of crack dynamics: phase field modeling
This thesis describes the behavior of cracks and pores under the influence of elastic and curvature effects. In a continuum theory approach, these structure deformations are treated as free moving boundaries. Our investigation start with well established sharp interface equations for which no fully …