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 9 of 9 for “"Fine-grained complexity"”.

  1. Fine-Grained Complexity: Exploring Reductions and their Properties

    Η σχεδίαση αλγορίθμων αποτελεί ένα απο τα κύρια θέματα ενδιαφέροντος για τον τομέα της Πληροφορικής. Παρά τα πολλά αποτελέσματα σε ορισμένους τομείς, η προσέγγιση αυτή έχει πετύχει κάποια πρακτικά αδιέξοδα που έχουν αποδειχτεί προβληματικά στην πρόοδο του τομέα. Επίσης, οι κλασικές πρακτικές …

    athens Repository record for Fine-Grained Complexity: Exploring Reductions and their Properties (opens in a new tab)

  2. Algorithms, parallelism and fine-grained complexity for shortest path problems in sparse graphs

    … and distributed settings. We also present fine-grained reductions that establish fine-grained hardness for several problems related to shortest paths. In the sequential context, we consider the fine-grained complexity of sparse graph problems whose time complexities have stayed at Õ(mn) …

    texas Repository record for Algorithms, parallelism and fine-grained complexity for shortest path problems in sparse graphs (opens in a new tab)

  3. Distributed fault tolerant distance computation in graphs : algorithms and lower bounds

    … little was known about the distributed round complexity of these problems. In many cases, we obtain near optimal bounds for our problems. The sequential fine-grained complexity of these fault-tolerant path problems is closely related to other fundamental graph problems, such as the Minimum …

    texas Repository record for Distributed fault tolerant distance computation in graphs : algorithms and lower bounds (opens in a new tab)

  4. Theoretical Bounds and Systems Development for Exact/Approximate Multiplicities in Bag PDBs

    … under bag semantics which has PTIME data complexity. However, does this imply that bag probabilistic databases are practical? We strive to answer this question from both a theoretical as well as a systems perspective. The problem of computing the marginal probability of a tuple in the …

    buffalo Repository record for Theoretical Bounds and Systems Development for Exact/Approximate Multiplicities in Bag PDBs (opens in a new tab)

  5. Scheduling and Packing Problems

    … 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 efficient when …

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

  6. Database-Inspired Reasoning Problems in Description Logics With Path Expressions

    … of the “expressive power versus computational complexity” trade-off for the Z family of DLs, we provide a more fine-grained complexity analysis for the query entailment problem over ontologies. In the thesis we focus on tame fragments of ZOIQ, namely the fragments in which either one the three …

    qucosa-diss

  7. Structural parameters, tight bounds, and parameterized approximation

    … problems through structural parameterization andfine-grained analysis. For our problems of study we (i) locate the boundary betweenfixed-parameter tractability and W[1]-hardness, by giving improved hardness reductionsand designing new FPT algorithms; (ii) match natural DP algorithms with tight …

    greece Repository record for Structural parameters, tight bounds, and parameterized approximation (opens in a new tab)