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 6 of 6 for “"graph orientations"”.
-
Efficient Sampling and Counting of Graph Structures related to Chordal Graphs
… The problems of counting and sampling of graph structures on different types of graphs have been studied for decades for their great importance in areas like complexity theory and statistical physics. For many graph structures such as independent sets and acyclic orientations, it is widely …
-
Combinatorial divisor theory for graphs
… simple game played on the vertices of a graph, which was independently discovered in probability theory, poset theory, graph theory, and statistical physics. In recent years, chip-firing has been employed in the development of a theory of divisors on graphs analogous to the classical …
-
Fair division of indivisible items
… Additionally, we study a recently-introduced graphical model that represents the fair division problem as a multigraph, in which vertices correspond to agents and edges correspond to items. The graphical model stipulates that an item can have non-zero marginal utility to an agent only if its …
-
Bounds on the maximal number of graph embeddings
… the embeddings (or equivalently realizations) of graphs in an euclidean space or a manifold.If the number of realizations satisfying edge length constraints is finite up to rigid motions, then the embedding is called rigid, otherwise it is called flexible. These embeddings can be related to the …
-
Arboricity and transversal problems on bounded degree graphs
… arboricity and transversal problems on graphs in a bounded degree setting. We pay particular attention to problems involving both the maximum degree and maximum density of the graphs. The first topic is bounded degree arboricity. The arboricity of a multigraph $G$ is the minimum number …
-
Obstructions for local tournament orientation completions
… problem for a hereditary class C of oriented graphs asks whether a given partially oriented graph can be completed to a graph belonging to C. This problem was introduced recently and is a generalization of several existing problems, including the recognition problem for certain classes of …