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 11 of 11 for “"degree bounded"”.

  1. Survivable network design problems with element and vertex connectivity requirements

    In this thesis, we consider degree-bounded element-connectivity Survivable Network Design Problem (Elem-SNDP) and degree-bounded Rooted k-outconnectivity Problem. We suggest bicriteria approximation algorithms that are motivated by Ene and Vakilian's work in [1] and Lau and Zhou's work in [2]. The …

    uiuc Repository record for Survivable network design problems with element and vertex connectivity requirements (opens in a new tab)

  2. Primal-Dual Techniques for Online Algorithms and Mechanisms

    … constraints. We initiate the study of degree-bounded graph optimization problems in the online setting by designing an online algorithm with a tight competitive ratio for the degree-bounded Steiner forest problem. We hope these techniques establishes a starting point for the analysis of …

    maryland Repository record for Primal-Dual Techniques for Online Algorithms and Mechanisms (opens in a new tab)

  3. Iterative Rounding Approximation Algorithms in Network Design

    … can construct a (2,2B + 3)-approximation for the degree bounded ELC problem, and this thesis provides the proof. We provide some structural results for basic feasible solutions of the Prize-Collecting Steiner Tree problem, and introduce a new problem that arises, which we call the Prize-Collecting …

    waterloo Repository record for Iterative Rounding Approximation Algorithms in Network Design (opens in a new tab)

  4. Algebraic degrees of stretch factors in mapping class groups

    … a stretch factor is an algebraic integer with degree bounded above by 6g-6. However, little is known about which degrees occur. Using train tracks on surfaces, we explicitly construct pseudo-Anosov maps on Sg with orientable foliations whose stretch factor \lambda has algebraic degree 2g. …

    gatech Repository record for Algebraic degrees of stretch factors in mapping class groups (opens in a new tab)

  5. New Algorithmic Solutions for Some Clustering and Network Design Problems

    … location problem. The second part is devoted to degree-bounded network design problems. The degree constraints require the degree of each node being bounded by certain quantity, which often makes a network design problem much harder. We aim to design algorithms for several fundamental network …

    buffalo Repository record for New Algorithmic Solutions for Some Clustering and Network Design Problems (opens in a new tab)

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

    … search space. For Vertex Cover on graphs with degree bounded by three, we present a still better algorithm that runs in time O(1.194k + kn), based on an “almost-global” analysis of the search tree. We also show that an important structural property of the underlying graphs – the …

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

  7. Critical Exponents and Stabilizers of Infinite Words

    … exponents of such words are algebraic, of a degree bounded by the alphabet size. Under certain conditions, our proof implies an algorithm for computing the critical exponent. We demonstrate our method by computing the critical exponent of some families of infinite words. In particular, in …

    waterloo Repository record for Critical Exponents and Stabilizers of Infinite Words (opens in a new tab)

  8. An information theoretic approach to structured high-dimensional problems

    … discrete and Gaussian Markov networks based on degree-bounded graphs. The problem of accurately learning the structure of discrete Markov networks, based on power-law graphs generated from the con figuration model, is also studied. The eff ect of power-law exponent value on the hardness of the …

    texas Repository record for An information theoretic approach to structured high-dimensional problems (opens in a new tab)

  9. Routing, Scheduling, and Sorting in Consolidated Networks

    … departure times at the majority of the high-degree nodes in the network, an aspect characteristic of region-based networks. A second challenge is handling static storage constraints without leading to a weak relaxation in each iteration. To mitigate these limitations, an arc-based DDD …

    waterloo Repository record for Routing, Scheduling, and Sorting in Consolidated Networks (opens in a new tab)