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 “"Graph coloring problems"”.
-
Graph Coloring Problems and Group Connectivity
… ≥ 2, there exists a finite family F = F(p, t) of graphs that do not have a mod (2p + 1)-orientation, such that every graph G with independence number at most t either admits a mod (2p+1)-orientation or is contractible to a member in F. In particular, the graph family F(p, 2) is determined, and our …
-
On probabilistic, planar, and descriptive graph coloring problems
We investigate graph coloring problems from the perspective of three different types of graphs: graphs with forbidden bipartite subgraphs; planar graphs; and Borel graphs that are line graphs. We start with studying graph with forbidden bipartite subgraphs. We say a graph is $F$-free if it contains …
-
Scheduling in computer and communication systems and generalized graph coloring problems
… with weighted generalizations of the classical graph coloring problems motivated by scheduling arising in computer and communication systems. The most general problems we attack are called bounded max-vertex/edge-coloring problems and take as input a vertex/edge weighted graph and a bound b. In …
-
Directed acyclic constrained connectivity: complexity and applications
In this thesis we will explore a new problem on Graph Theory named Directed Acyclic Constrained Connectivity. Directed Acyclic Constrained Connectivity is a modification of (s, t)-Connectivity where we introduce constraints that restrict edge use. We show that Directed Acyclic Constrained …
-
Bi-directional determination of sparse Jacobian matrices : algorithms and lower bounds
… in many large-scale scientific and engineering problems. It is known that estimation of non-zeroes of a matrix can be viewed as a graph coloring problem. Due to the presence of dense rows or dense columns, unidirectional partitioning does not always give good results. Bi-Directional partitioning …
-
Αλγόριθμοι και περιπλοκότητα: χρωματισμοί γράφων και υπεργράφων
We study several vertex coloring problems for graphs and hypergraphs. We concentrate on conflict-free coloring. The conflict-free coloring problem has applications in efficient frequency assignment in cellular networks. We show the relation of conflict-free coloring paths of graphs with other graph …
-
Hypercube coloring and the structure of binary codes
A coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices are given the same color. The chromatic number of a graph is the least number of colors needed to color all of its vertices. Graph coloring problems can be applied to many real world applications, such …
-
Optimization of niobium oxide-based threshold switches for oscillator-based applications
… networks as well as their performance in solving graph coloring problems. Furthermore, strategies to adapt the threshold voltage to the switching characteristics of a tantalum oxide-based non-volatile resistive switch and a non-volatile phase change cell, to enable their application as selector …
-
Convex Algebraic Geometry Approaches to Graph Coloring and Stable Set Problems
… solution methods for combinatorial optimization problems involve formulations that make use of Systems of Linear Equations, Linear Programs (LPs), Semidefinite Programs (SDPs), and more generally, Conic and Semi-algebraic Programs. Although, generality often implies flexibility and power in the …
-
Constraint satisfaction problems: probabilistic approach and applications to social choice theory
… we work in one of the most well studied class of problems in Computer Science, that of Constraint Satisfaction Problems (CSPs). In one of their usual formulations, CSPs consist of a set of variables that take values in a common domain set. Groups of variables are tied by constraints that restrict …