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 10 of 10 for “"Hypergraph coloring"”.

  1. On Some Hypergraph Coloring Algorithms

    … containing no copies of the Fano plane as a subhypergraph. Since the Fano plane is not bipartite, it holds that B_n ⊆ F_n, which Person and Schacht proved is nearly an equality (in a sense made precise later). They also established an algorithm which properly and minimally colors a given H ∈ F_n …

    usf Repository record for On Some Hypergraph Coloring Algorithms (opens in a new tab)

  2. Phylogenetic decisiveness and no-rainbow hypergraph coloring

    … Here we relate the decisiveness problem to a hypergraph coloring problem. We use this connection to (1) show that the decisiveness problem is co-NP complete, (2) obtain lower bounds on the amount of coverage needed to achieve decisiveness, (3) devise an exact algorithm for decisiveness, (4) …

    iastate Repository record for Phylogenetic decisiveness and no-rainbow hypergraph coloring (opens in a new tab)

  3. Efficient derandomization of the Lovász Local Lemma and applications to coloring and packing problems

    … packing type problems: (i) a particular kind of hypergraph coloring problem, and (ii) vector packing problem. The hypergraph coloring problem is connected to the resource constrained scheduling problem and vector packing is a particular multi-dimensional generalization of the well known bin …

    cau-kiel Repository record for Efficient derandomization of the Lovász Local Lemma and applications to coloring and packing problems (opens in a new tab)

  4. An Overview of the Constructive Local Lemma

    … provide an implementation of the algorithm to a hypergraph coloring problem.

    south-carolina Repository record for An Overview of the Constructive Local Lemma (opens in a new tab)

  5. Intersperse Coloring

    In this thesis, we introduce the intersperse coloring problem, which is a generalized version of the hypergraph coloring problem. In the intersperse coloring problem, we seek a coloring that assigns at least l different colors to each hyperedge of the input hypergraph, where l is an input parameter …

    waterloo Repository record for Intersperse Coloring (opens in a new tab)

  6. A Synopsis of the Lovász Local Lemma: Generalizations, Applications, and Algorithms

    … with the motivation rooted in Ramsey theory, hypergraph coloring problems, and others, we explore how the Lovász Local Lemma transformed probabilistic existence proofs in Combinatorics and explore its applications. We also examine some generalizations of the lemma, including the algorithmic …

    unr Repository record for A Synopsis of the Lovász Local Lemma: Generalizations, Applications, and Algorithms (opens in a new tab)

  7. Algorithms and Generalizations for the Lovasz Local Lemma

    … This leads to improved bounds for k-SAT and hypergraph coloring among other applications. We describe an extension of the Moser-Tardos algorithm based on partial resampling, and use this to obtain better bounds for problems involving sums of independent random variables, such as column-sparse …

    maryland Repository record for Algorithms and Generalizations for the Lovasz Local Lemma (opens in a new tab)

  8. Derandomizing Concentration Inequalities with dependencies and their combinatorial applications

    … In Chapter 8, we analyze the constrained hypergraph coloring problem given in Ahuja and Srivastav (2002), which generalizes both the property B problem for the non-monochromatic 2-coloring of hypergraphs and the multidimensional bin packing problem using the bounded differences inequality …

    cau-kiel Repository record for Derandomizing Concentration Inequalities with dependencies and their combinatorial applications (opens in a new tab)

  9. Formal group laws and hypergraph colorings

    … group laws and chromatic symmetric functions of hypergraphs, two seemingly unrelated topics in the theory of symmetric functions. A formal group law is a symmetric function of the form $f(f^{-1}(x_1) + f^{-1}(x_2) + \cdots)$ for a formal power series $f(x) \in \mathbb{Q}[[x]]$. A …

    washington Repository record for Formal group laws and hypergraph colorings (opens in a new tab)

  10. Coloring and constructing (hyper)graphs with restrictions

    … questions regarding the existence of graphs and hypergraphs with certain coloring properties and other structural properties. In Chapter 2 we consider color-critical graphs that are nearly bipartite and have few edges. We prove a conjecture of Chen, Erdős, Gyárfás, and Schelp concerning the …

    uiuc Repository record for Coloring and constructing (hyper)graphs with restrictions (opens in a new tab)