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 “"Vertex degree"”.
-
Matching problems in hypergraphs
… n is a multiple of 3 and large, and the minimum vertex degree of H is greater than {(n-1) choose 2} - {2n/3 choose 2}, then H contains a perfect matching. We show that for sufficiently large n divisible by 3, if F_1, ..., F_{n/3} are 3-uniform hypergraphs with a common vertex set and the minimum …
-
Embedding problems in graphs and hypergraphs
… their generalisations. We determine the minimum vertex degree that ensures a perfect matching in a 3-uniform hypergraph, thereby answering a question of Hàn, Person and Schacht. We say that a graph \(G\) has a perfect \(H\)-packing (also called an \(H\) - factor) if there exists a set of disjoint …
-
Three-dimensional visualization of multi-layered graphs with application to communications
… algorithm for displaying any graph of any vertex degree. The above algorithm can be implemented to display graph in 3D space without edge crossing. The number of edge bends produced by the algorithm does not excess two. The average time complexity of the Incremental Projection Algorithm is …
-
Approximation algorithms for packing and scheduling problems
… edges of a bipartite graph equals the maximum vertex degree. For the weighted generalization, a longstanding open question is to determine the minimum number of colors as a function of n, the maximum total weight adjacent to any vertex. Our main contribution is to show that 2.557n + o(n) colors …
-
Linear Orderings of Sparse Graphs
… guarantees especially for graphs with bounded vertex degree. This thesis fills this gap in multiple respects: We establish necessary conditions for a linear ordering (and thereby also for a feedback arc set) to be optimal, which provide new and fine-grained insights into the combinatorial …
-
Chromatic scheduling of dynamic data-graph computations
… alternative is chromatic scheduling which uses a vertex coloring of the conflict graph to divide data-graph updates into sets which may be parallelized without races. To date, however, only static data-graph computations, which do not schedule updates at runtime, have employed chromatic …
-
Combinatorics of colored factorizations, flow polytopes and of matrices over finite fields
… the number of planar trees and cacti with given vertex degree distribution calculated by Goulden and Jackson. In the second part we establish the relationship between volumes of ow polytopes associated to signed graphs and the Kostant partition function. A special case of this relationship, …
-
The impact of author name disambiguation on knowledge discovery from large-scale scholarly data
… generating the power-law distribution of vertex degree and to false validation of theories about the choice of collaborators in scientific research. This may result in ill-informed decisions about research policy and resource allocation. Besides measuring the impact of name ambiguity on …
-
New sublinear methods in the struggle against classical problems
… optimization problems considered by us include vertex cover, maximum matching, and dominating set. A graph algorithm is traditionally called a constant-time algorithm if it runs in time that is a function of only the maximum vertex degree, and in particular, does not depend on the number of …
-
On vertex degrees, graph decomposition, and circular chromatic Ramsey number
In this thesis, we study extremal problems about vertex degrees and a variant of Ramsey number of graphs, and also structural problems about graph decomposition. In a list (d_1,...,d_n) of positive integers, let r and s denote the largest and smallest entries. A list is gap-free if each integer …
-
Theoretical and Algorithmic Solutions for Null models in Network Theory
… edges are rewired at random, with each expected vertex degree matching the degree of the vertex in the original graph. Although aimed at building a reference for the community detection, this approach will play a key role in one of the model considered in this thesis. Note that, although being …