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"”.

  1. 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 …

    utc Repository record for On the minimum rank of certain graphs with path cover number 2 (opens in a new tab)

  2. Αλγόριθμοι και αποτελέσματα 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 …

    greece Repository record for Αλγόριθμοι και αποτελέσματα NP-πληρότητας για προβλήματα χρωματισμού και επικάλυψης με μονοπάτια σε τέλεια γραφήματα (opens in a new tab)

  3. 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 …

    regina Repository record for On the class of graphs ZP (opens in a new tab)

  4. 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>

    iastate Repository record for Zero forcing number: Results for computation and comparison with other graph parameters (opens in a new tab)

  5. 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 …

    gatech Repository record for An Optimization Framework for Embedded Processors with Auto-Modify Addressing Modes (opens in a new tab)

  6. 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 …

    byu Repository record for The Relationship Between the Minimal Rank of a Tree and the Rank-Spreads of the Vertices and Edges (opens in a new tab) Download PDF for The Relationship Between the Minimal Rank of a Tree and the Rank-Spreads of the Vertices and Edges (opens in a new tab)

  7. 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 …

    uiuc Repository record for Matchings, Connectivity, and Eigenvalues in Regular Graphs (opens in a new tab)

  8. 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 …

    regina Repository record for Zero Forcing Sets for Graphs (opens in a new tab) Download PDF for Zero Forcing Sets for Graphs (opens in a new tab)

  9. 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 …

    fu-berlin Repository record for Contributions to the detection of non-reference sequences in population-scale NGS data (opens in a new tab)

  10. 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 …

    duke Repository record for Algorithms for Geometric Matching, Clustering, and Covering (opens in a new tab)

  11. 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 …

    byu Repository record for The Minimum Rank Problem for Outerplanar Graphs (opens in a new tab) Download PDF for The Minimum Rank Problem for Outerplanar Graphs (opens in a new tab)