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 14 of 14 for “"Path cover"”.
-
On the minimum rank of certain graphs with path cover number 2
… of a graph. We define a family of graphs with path cover number two and consider restrictions on the structure and minimum rank of these types of graphs. We consider a sub-family of these graphs and calculate the zero-forcing number and the positive semidefinite minimum rank. We also conjecture …
-
Αλγόριθμοι και αποτελέσματα NP-πληρότητας για προβλήματα χρωματισμού και επικάλυψης με μονοπάτια σε τέλεια γραφήματα
This work focuses on the complexity status of path cover and coloring problems on classes of perfect graphs. In particular, it deals with designing and analyzing graph algorithms for these problems or, for the cases where this is not possible, with providing NP-completeness results. Most of our …
-
On the class of graphs ZP
… a graph made up of vertices V and edges E. The path cover number and zero forcing number are two graph parameters that have been of recent research interests and are closely related. Zero forcing at it’s most rudimentary, is a graph colouring game. There is a significant preexisting body of work …
-
Zero forcing number: Results for computation and comparison with other graph parameters
… The zero forcing number is compared to the path cover number and the maximum nullity with equality of zero forcing number and path cover number shown for all cacti and equality of zero forcing number and maximum nullity shown for a subset of cacti.</p>
-
The Minimum Rank, Inverse Inertia, and Inverse Eigenvalue Problems for Graphs
… parameters, the zero forcing number and the path cover number, related to the minimum rank problem.
-
An Optimization Framework for Embedded Processors with Auto-Modify Addressing Modes
… an access graph and finding the maximum weight path cover to find an optimized stack variables layout. We take this further by using coalescing, addressing mode selection and offset registers to find further opportunities for reducing the number of load-address instructions required. We also …
-
The Relationship Between the Minimal Rank of a Tree and the Rank-Spreads of the Vertices and Edges
… well-known result that for a tree the sum of its path cover number and minimal rank is equal to the number of vertices in the tree. The rank-spread of a vertex v of G is the difference between the minimal ranks of G and G - v, the graph obtained by deleting v and all its incident edges from G. The …
-
Matchings, Connectivity, and Eigenvalues in Regular Graphs
… including the Chinese postman problem, the path cover number, the average edge-connectivity, and the number of perfect matchings. In Chapter 5, we study an $r$-dynamic coloring problem and give the relationship between the $r$-dynamic chromatic number and the chromatic number in regular …
-
Zero Forcing Sets for Graphs
… equality between the zero forcing number and the path cover number for a new family of graphs. In addition, we establish a connection between the zero forcing number and the chromatic number of graphs. With regard to the positive zero forcing number, we introduce the concept of forcing trees in a …
-
Contributions to the detection of non-reference sequences in population-scale NGS data
… and requires high-quality sequence data at high coverage. Previous studies have demonstrated how sequence data of multiple genomes can be combined for the reliable detection of NRS variants. However, the algorithms proposed in these studies have a limited capability to process large sets of …
-
Algorithms for Geometric Matching, Clustering, and Covering
… part of the thesis considers the problem of covering shortest paths in a road network, motivated by an EV charging station placement problem. More specifically, a subset of vertices in the road network are selected to place charging stations so that every shortest path contains enough …
-
The Minimum Rank Problem for Outerplanar Graphs
… the minimum rank problem for this class. The path cover number of a graph, denoted P(G), is the minimum number of vertex-disjoint paths needed to cover all the vertices of G. We show that for all outerplanar graphs G, P(G)is greater than or equal to M(G). We identify a subclass of outerplanar …