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 16 of 16 for “"fixed-parameter tractability"”.
-
Directed Graphs: Fixed-Parameter Tractability & Beyond
… 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. In parameterized complexity, each problem comes along with a secondary measure k which is called the …
-
Algorithms for minimum bipartite fill-in and the gene-duplication problem
… the gene-duplication problem. We establish the fixed parameter tractability of the minimum bipartite fill-in problem and develop a faster local search algorithm which speeds up heuristics for the gene-duplication problem.</p>
-
A Reconfigurable Computing Solution to the Parameterized Vertex Cover Problem
… past two decades in the field of computational intractability. This thesis explores parallel implementations on a RC (reconfigurable computing) platform for FPT (<em>fixed-parameter tractable</em>) algorithms.</p> <p>Reconfigurable hardware implementations of algorithms for solving NP-Complete …
-
Consequence-based reasoning for ontology classification
… and thus obtain what we believe are the first fixed-parameter tractability results for subsumption reasoning in DLs.</p>
-
Graph-Theoretical Tools for the Analysis of Complex Networks
… design, a study of the two core tenets of fixed parameter tractability (branching and kernelization) is considered in the context of a parallel implementation of vertex cover. Results of testing on a wide variety of graphs derived from both real and synthetic data are presented. It is shown …
-
Tractable cognition : complexity theory in cognitive psychology
… first, called the P-Cognition thesis, defines tractability as polynomial-time computability and is the dominant view in cognitive science today. The second, called the FPT-Cognition thesis, is proposed by the author and defines tractability as fixed-parameter tractability for some “small” input …
-
Odd multiway cut in directed acyclic graphs
… multiway node cut and odd multiway edge cut are fixed-parameter tractable (FPT) when parameterized by the size of the solution in undirected graphs. In this work, we focus on directed acyclic graphs (DAGs) and design a fixed-parameter algorithm. Our main contribution is a broadening of the …
-
Parameterized Algorithms for Integer Linear Programs and Their Applications for Allocation Problems
… polynomial time. The second strategy is called Fixed-Parameter Tractability (FPT) and considers parameters of the instance to capture the hardness of the problem and by that, obtain efficient algorithms with respect to the remaining input. This thesis employs both strategies jointly to develop …
-
On Covering Points with Conics and Strips in the Plane
… the techniques used to study NP-hard problems is Fixed Parameter Tractability (FPT), where, in addition to input size, a parameter k is provided for input instance. We ask to solve the problem with respect to k, such that the running time is a function in both n and k, strictly polynomial in n, …
-
Scalable Graph Algorithms with Applications in Genetics
… memory archi- tectures, (b) the theory of fixed parameter tractability, and (c) a novel bitmap data representation scheme for memory and search space reduction. An implementation of the parallel algorithm scales linearly to at least 64 processors.</p> <p>Maximal biclique finding on …
-
Heterogeneous spreading processes on graphs as models of contagion
… identify tractable subclasses and obtain fixed-parameter tractability results. Specifically, we give monadic second-order formulations on bounded treewidth graphs and provide fixed-parameter tractable algorithms parameterised by structural measures including vertex cover number and …
-
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 …
-
Complexity of optimally defending and attacking a network
… analysis of these problems and provide several intractability results. We complement these results by providing exact parameterized algorithms to compute optimal strategies for both the attacker and defender.
-
On Reconfiguration Problems: Structure and Tractability
… to embark on a systematic investigation of the tractability and structural properties of such problems under both classical and parameterized complexity assumptions. Parameterized complexity is another framework which has become an essential tool for researchers in computational complexity …
-
On Token Movement Problems
… static model of the world. Specifically, given a fixed unchanging input instance, e.g., a graph, the usual goal is to compute a fixed subset of vertices or edges that minimizes or maximizes some objective function. In addition to unchanging instances, the static model ignores the potential …