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 20 of 46 for “"parameterized complexity"”.
-
Characterizing Hardness in Parameterized Complexity
Parameterized complexity theory relaxes the classical notion of tractability and allows to solve some classically hard problems in a reasonably efficient way. However, many problems of interest remain intractable in the context of parameterized complexity. A completeness theory to categorize such …
-
Systematic parameterized complexity analysis in computational phonology
… most naturally addressed within the theory of parameterized computational complexity developed by Downey and Fellows. This thesis considers the merits of a systematic parameterized complexity analysis in which results are derived relative to all subsets of a specified set of aspects of a given …
-
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 …
-
Parameterized complexity and polynomial-time approximation schemes
… among them are approximation algorithms and parameterized algorithms. The study of approximation algorithms tries to find good enough solutions instead of optimal solutions in polynomial time, while parameterized algorithms try to give exact solutions when a natural parameter is small. In this …
-
Parameterized complexity in graph theory, logic and machine learning
This thesis extends the scope of Parameterized Complexity beyond its traditional boundaries, demonstrating its ability to manage computational intractability in diverse settings. While structural parameters like treewidth are typically associated with graph algorithms, we expand their application …
-
On the parameterized complexity of finding short winning strategies in combinatorial games
… any opponent may make in response. The classical complexity of deciding whether a winning strategy exists for a given position in some combinatorial game has been well-studied both in general and for many specific combinatorial games. The vast majority of these problems are, depending on the …
-
Μερικές διατάξεις και αλγόριθμοι σε γραφήματα
… inuenced the development of a new branch of Complexity, namelythe Parameterized Complexity Theory, introduced by R. Downey and M.Fellows.In this doctoral thesis we deal with a series of issues in Graph MinorTheory and Parameterized Complexity as well as the dependence of thesetwo areas.
-
Directed Graphs: Fixed-Parameter Tractability & Beyond
… an NP-hard problem exactly. However, classical complexity measures the running time as a function of only the overall input size. The paradigm of <italic>parameterized complexity</italic> was introduced by Downey and Fellows to allow for a more refined multivariate analysis of the running time. …
-
Parameterised complexity analysis of evolutionary algorithms for combinatorial optimization problems
… quite challenging. In this thesis we analyse the parameterized complexity of evolutionary algorithms on combinatorial optimization problems. Studying the parameterized complexity of these algorithms can help us understand how different parameters of problems influence the runtime behaviour of the …
-
Kernelization and Enumeration: New Approaches to Solving Hard Problems
… approaches meet the practical needs. Recently parameterized computation and complexity has attracted a lot of attention and been a fruitful branch of the study of efficient algorithms. By taking advantage of the moderate value of parameters in many practical instances, we can design efficient …
-
An integrated complexity analysis of problems from computational biology
We perform an Integrated complexity analysis on a number of combinatorial problems arising from the field of computational biology. The classic framework of NP-completeness, algorithmic design techniques for bounded width graphs, and parameterized computational complexity together provide a clear …
-
Representations and Parameterizations of Combinatorial Auctions
… if and only if their bid graphs are isomorphic. Parameterized complexity theory can be used to further distinguish between NP-hard problems. In order to make use of parameterized complexity theory in the investigation of a problem, we aim to find one or more parameters that describe some aspect …
-
Graph Editing to a Given Neighbourhood Degree List is Fixed-Parameter Tractable
… is NP-complete and study its parameterized complexity. In parameterized complexity, a problem is said to be fixed-parameter tractable with respect to a parameter if it has a solution whose running time is a function that is polynomial in the input size but possibly …
-
On parameterized counting
… have tried to analyze the intrinsic hardness of parameterized counting problems. We have analyzed the parameterized complexity of #W(P)-complete problems. We proved that, (under some complexity theoretic hypothesis): <br>1. Any #W(P)-complete is harder than any problem in the A hierarchy. <br>2. …
-
Parameterized Approaches for Large-Scale Optimization Problems
… optimization problems from the perspective of parameterized complexity. The usefulness of this type of analysis is twofold. First, it can lead to efficient algorithms for large-scale problem instances. Second, the analysis can provide a rigorous explanation for why challenging problems might …
-
On Token Movement Problems
… This thesis contributes to the computational complexity landscape for these transformation problems. For solution discovery problems where the target property is to form a matching, vertex/edge cut, or shortest path, we show that even though these properties are efficiently computable in the …
-
Parameterized Enumeration of Neighbour Strings and Kemeny Aggregations
… approaches to enumeration problems in the parameterized complexity setting. We obtain competitive parameterized algorithms to enumerate all, as well as several of, the solutions for two related problems Neighbour String and Kemeny Rank Aggregation. In both problems, the goal is to find a …
Page 1 of 3