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 27 for “"Parameterized algorithms"”.

  1. Approximation and Parameterized Algorithms for Scheduling Problems

    … part, we give constant-factor approximation algorithms for two scheduling problems, known as Coupled Task Scheduling and Preemptive Batch Scheduling. In the second part, we exclusively look at the problem of Scheduling on Uniform Machines, but with different objective functions, in different …

    cau-kiel Repository record for Approximation and Parameterized Algorithms for Scheduling Problems (opens in a new tab)

  2. Parameterized algorithms and computational lower bounds: a structural approach

    … are unlikely to be solved by polynomial-time algorithms. There are several ways to cope with the NP-hardness of a certain problem. The most popular approaches include heuristic algorithms, approximation algorithms, and randomized algorithms. Recently, parameterized computation and complexity …

    tamu Repository record for Parameterized algorithms and computational lower bounds: a structural approach (opens in a new tab)

  3. Randomized and Deterministic Parameterized Algorithms and Their Applications in Bioinformatics

    Parameterized NP-hard problems are NP-hard problems that are associated with special variables called parameters. One example of the problem is to find simple paths of length k in a graph, where the integer k is the parameter. We call this problem the p-path problem. The p-path problem is the …

    tamu Repository record for Randomized and Deterministic Parameterized Algorithms and Their Applications in Bioinformatics (opens in a new tab)

  4. Alliances In Graphs: Parameterized Algorithms And On Partitioning Series-parallel Graphs

    … In this thesis, we will present a variety of algorithms for finding alliances in different families of graphs with a running time that is polynomial in terms of the size of the input, and allowing exponential running time as a function of a chosen parameter. This study is guided by the theory …

    ucf Repository record for Alliances In Graphs: Parameterized Algorithms And On Partitioning Series-parallel Graphs (opens in a new tab)

  5. Parameterized Algorithms for Integer Linear Programs and Their Applications for Allocation Problems

    … The first approach aims to design approximation algorithms, that is, we are content to find good, but non-optimal solutions in 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 …

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

  6. Kernelization and Enumeration: New Approaches to Solving Hard Problems

    … problems are unlikely to admit polynomial-time algorithms. However since many NP-Hard problems are of practical significance, different approaches are proposed to solve them: Approximation algorithms, randomized algorithms and heuristic algorithms. None of the approaches meet the practical …

    tamu Repository record for Kernelization and Enumeration: New Approaches to Solving Hard Problems (opens in a new tab)

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

    waterloo Repository record for Parameterized Enumeration of Neighbour Strings and Kemeny Aggregations (opens in a new tab)

  8. Parameterized complexity and polynomial-time approximation schemes

    … NPhard problems, 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 …

    tamu Repository record for Parameterized complexity and polynomial-time approximation schemes (opens in a new tab)

  9. Clustering and Inconsistent Information: A Kernelization Approach

    … linear size with very small constants. Better parameterized algorithms are also designed based on the kernels for the last two problems. Finally, some concluding remarks on possible directions for future research are briefly mentioned.

    tamu Repository record for Clustering and Inconsistent Information: A Kernelization Approach (opens in a new tab)

  10. Models and Algorithms for Real-Time Systems

    We apply the framework of parameterized algorithms to the FP (fixed-priority) and EDF (earliest- deadline-first) scheduling of recurrent (periodic and sporadic) task systems in a preemptive uniprocessor environment, which are fundamental models in real-time scheduling theory. We identify parameters …

    wustl Repository record for Models and Algorithms for Real-Time Systems (opens in a new tab)

  11. Generalizations of comparability graphs

    … optimization problems are solved by polynomial algorithms. It also has close connections with other classes of graphs, such as interval graphs, permutation graphs, and perfect graphs. In this dissertation, we define new measures for transitivity to generalize comparability graphs. We introduce …

    colostate Repository record for Generalizations of comparability graphs (opens in a new tab)

  12. Scheduling and Packing Problems

    … all instances in polynomial time. The goal of parameterized complexity - and this thesis - is to find out exactly what makes these problems difficult to solve and to identify special cases that can be solved efficiently. One part of this is finding algorithms with running times that are …

    cau-kiel Repository record for Scheduling and Packing Problems (opens in a new tab)

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

    waterloo Repository record for Graph Editing to a Given Neighbourhood Degree List is Fixed-Parameter Tractable (opens in a new tab)

  14. Efficient String and Graph Algorithms in Modern Settings

    … distance have been well-studied for decades, and algorithms for these problems have become established and widespread. In modern times, however, achieving even faster algorithms for more specific scenarios finds increasing value as dataset sizes become larger and computer application settings …

    maryland Repository record for Efficient String and Graph Algorithms in Modern Settings (opens in a new tab)

  15. Cuts and Partitions in Graphs/Trees with Applications

    … and algorithmic techniques that lead to improved parameterized algorithms, approximation algorithms, and kernelization algorithms for these problems. For the maximum agreement forest problem, we proceed from the bottommost level of trees and extend solutions to whole trees. With this technique, we …

    tamu Repository record for Cuts and Partitions in Graphs/Trees with Applications (opens in a new tab)

  16. Complexity of optimally defending and attacking a network

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

  17. Scalable algorithm designs for mining massive datasets

    … A broad topic of this thesis is to design algorithms that can practically solve a set of computationally-intractable problems under restrictive settings, using mathematical abstractions and computational tools. In particular, the problems of our interest include pattern detection in graphs …

    aalto Repository record for Scalable algorithm designs for mining massive datasets (opens in a new tab)

  18. Parameterized Approximation Results for Clustering and Graph Packing Problems

    … prompting the exploration of approximation algorithms and parameterized algorithms as possible approaches, among others. In recent times, the paradigm of parameterized approximation algorithms, which strike a balance between approximation and polynomial-time computability on instances with …

    aalto Repository record for Parameterized Approximation Results for Clustering and Graph Packing Problems (opens in a new tab)

  19. Design and Implementation of High Performance Algorithms for the (n,k)-Universal Set Problem

    … for biological subnetwork matching. There are algorithms implemented to solve the problem for k up to 13. The fastest implementation has running time O^*(4.32^k), which is slower than the best known algorithm of running time O^*(4^k). To implement the best known algorithm for the k-path …

    tamu Repository record for Design and Implementation of High Performance Algorithms for the (n,k)-Universal Set Problem (opens in a new tab)

Page 1 of 2