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 5 of 5 for “"optimal coloring"”.
-
Constant composition deletion correcting codes
… codes and show that they are asymptotically optimal and form an optimal coloring. There is a natural distance on compositions that provides a lower bound on deletion distance. Unrestricted deletion correcting codes can be constructed from the union of constant composition codes as long as the …
-
On hereditary graph classes defined by forbidding Truemper configurations: recognition and combinatorial optimization algorithms, and χ-boundedness results
… of the maximum clique, maximum stable set and optimal coloring problems restricted to these classes. Finally, we provide polynomial-time recognition algorithms for all of these classes, and we obtain χ-boundedness results.
-
Separability and Vertex Ordering of Graphs
… graph optimization problems, such as finding an optimal coloring, or a largest clique, can be solved by a divide-and-conquer approach. One such well-known technique is decomposition by clique separators where a graph is decomposed into special induced subgraphs along their clique separators. …
-
Various Algorithms for High Throughput Sequencing
… Weighted Sequence Graph representation of all optimal and near optimal alignments between the two reads sampled from a piece of DNA with k-mer filtering methods and spaced seeds to quickly generate candidate locations for the reads on the reference genome. Our method combines these approaches …
-
Improved implementation of some coloring algorithms for the determination of large and sparse Jacobian matrices
… implementation of a branch-and-bound type exact coloring algorithm with new tie-breaking strategies is provided. The results are supported by extensive numerical experiments with benchmarking instances from the literature.