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"”.

  1. 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 …

    maryland Repository record for Directed Graphs: Fixed-Parameter Tractability & Beyond (opens in a new tab)

  2. 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>

    iastate Repository record for Algorithms for minimum bipartite fill-in and the gene-duplication problem (opens in a new tab)

  3. 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 …

    ut-knoxville Repository record for A Reconfigurable Computing Solution to the Parameterized Vertex Cover Problem (opens in a new tab)

  4. 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>

    oxford Repository record for Consequence-based reasoning for ontology classification (opens in a new tab)

  5. 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 …

    utk-theses Repository record for Graph-Theoretical Tools for the Analysis of Complex Networks (opens in a new tab)

  6. 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 …

    uvic Repository record for Tractable cognition : complexity theory in cognitive psychology (opens in a new tab)

  7. 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 …

    uiuc Repository record for Odd multiway cut in directed acyclic graphs (opens in a new tab)

  8. 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 …

    cau-kiel Repository record for Parameterized Algorithms for Integer Linear Programs and Their Applications for Allocation Problems (opens in a new tab)

  9. 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, …

    tamu Repository record for On Covering Points with Conics and Strips in the Plane (opens in a new tab)

  10. 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 …

    utk-theses Repository record for Scalable Graph Algorithms with Applications in Genetics (opens in a new tab)

  11. 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 …

    glasgow Repository record for Heterogeneous spreading processes on graphs as models of contagion (opens in a new tab) Download PDF for Heterogeneous spreading processes on graphs as models of contagion (opens in a new tab)

  12. 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 …

    freiburg-diss Repository record for Model-checking problems, machines and parameterized complexity (opens in a new tab)

  13. 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.

    unsw Repository record for Complexity of optimally defending and attacking a network (opens in a new tab)

  14. 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 …

    waterloo Repository record for On Reconfiguration Problems: Structure and Tractability (opens in a new tab)

  15. 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 …

    waterloo Repository record for On Token Movement Problems (opens in a new tab)