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 20 of 89 for “"graph classes"”.

  1. Testing graph classes

    … class libraries. Code reuse implies that the classes being reused need to be well tested. We present a graph class used to store and traverse directed testgraphs as part of the TestGraph Methodology for testing of C++ classes. A testgraph is a partial model of the state-transition graph of the …

    uvic Repository record for Testing graph classes (opens in a new tab)

  2. Zombies and survivors on graph classes

    Zombies and Survivors is a two-player graph game introduced by Fitzpatrick et al. as a variant of Cops and Robbers. These games can be used to model situations involving pursuit-evasion or search-and-rescue. Two players take turns to move their pieces in a given graph, with the condition that the …

    manitoba Repository record for Zombies and survivors on graph classes (opens in a new tab)

  3. Connectivity and related properties for graph classes

    <p>There has been much recent interest in random graphs sampled uniformly from the set of (labelled) graphs on n vertices in a suitably structured class A. An important and well-studied example of such a suitable structure is bridge-addability, introduced in 2005 by McDiarmid et al. in the course …

    oxford Repository record for Connectivity and related properties for graph classes (opens in a new tab)

  4. Two graph classes with bounded chromatic number

    A class of graphs is said to be $\chi$-bounded with binding function $f$ if for every such graph $G$, it satisfies $\chi(G) \leq f(\omega(G)$, and polynomially $\chi$-bounded if $f$ is a polynomial. It was conjectured that chair-free graphs are perfectly divisible, and hence admit a quadratic …

    gatech Repository record for Two graph classes with bounded chromatic number (opens in a new tab)

  5. Generation of Graph Classes with Efficient Isomorph Rejection

    … thesis, efficient isomorph-free generation of graph classes with the method of generation by canonical construction path(GCCP) is discussed. The method GCCP has been invented by McKay in the 1980s. It is a general method to recursively generate combinatorial objects avoiding isomorphic copies. …

    anu Repository record for Generation of Graph Classes with Efficient Isomorph Rejection (opens in a new tab)

  6. Recoloring in Hereditary Graph Classes: Structure and Decomposition

    … this thesis we study reconfiguration problems in graph theory. A reconfiguration problem is generally defined on the solution space of a problem for which a configuration can be defined as a feasible solution, for example, a coloring of a graph. In Chapters 1 through 4 we study the reconfiguration …

    wilfrid-laurier Repository record for Recoloring in Hereditary Graph Classes: Structure and Decomposition (opens in a new tab) Download PDF for Recoloring in Hereditary Graph Classes: Structure and Decomposition (opens in a new tab)

  7. Structural Characterisations of Hereditary Graph Classes and Algorithmic Consequences

    … onthe parity of its length. Many interesting classes of graphs are defined by excluding (possibly among other graphs) holes of certain lengths. Most famously perhaps is the class of Berge graphs, which are the graphs that contain no odd hole and no complement of an odd hole. A graph is perfect …

    whiterose Download PDF for Structural Characterisations of Hereditary Graph Classes and Algorithmic Consequences (opens in a new tab)

  8. Utilizing graph classes for community detection in social and complex networks

    … This thesis studies problems related to graph clustering, motivated by the social networking problem of community detection. One main contribution of this thesis is a new definition of a specific kind of family-like community, accompanied by theoretical and computational justifications. …

    ubc Repository record for Utilizing graph classes for community detection in social and complex networks (opens in a new tab) Download PDF for Utilizing graph classes for community detection in social and complex networks (opens in a new tab)

  9. On the computability of obstruction sets for well-quasi-ordered graph classes

    … (ΘΕΓ), των Neil Robertson και Paul Seymour (Graph Minor Theorem) εγγυάται πως κάθε κλάση κλειστή ως προς τη σχέση των ελασσόνων έχει πεπερασμένο σύνολο παρεμόδησης. Αν η C είναι μια τέτοια κλάση, τότε το σύνολο παρεμπόδησης της C είναι το ελαχιστικό σύνολο γραφημάτων H έτσι ώστε, ένα γράφημα …

    athens Repository record for On the computability of obstruction sets for well-quasi-ordered graph classes (opens in a new tab)

  10. A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes

    The direct sum of a finite number of graph classes H_1, ..., H_k is defined as the set of all graphs formed by taking the union of graphs from each of the H_i. The join of these graph classes is similarly defined as the set of all graphs formed by taking the join of graphs from each of the H_i. In …

    byu Repository record for A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes (opens in a new tab) Download PDF for A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes (opens in a new tab)

  11. On hereditary graph classes defined by forbidding Truemper configurations: recognition and combinatorial optimization algorithms, and χ-boundedness results

    Truemper configurations are four types of graphs that helped us understand the structure of several well-known hereditary graph classes. The most famous examples are perhaps the class of perfect graphs and the class of even-hole-free graphs: for both of them, some Truemper configurations are …

    whiterose Download PDF for On hereditary graph classes defined by forbidding Truemper configurations: recognition and combinatorial optimization algorithms, and χ-boundedness results (opens in a new tab)

  12. Rainbow Colorings in Graphs

    In this thesis, we deal with rainbow colorings of graphs. We engage not with the rainbow connection number but with counting of rainbow colorings in graphs with k colors. We introduce the rainbow polynomial and prove some results for some special graph classes. Furthermore, we obtain bounds for the …

    qucosa-diss

  13. On the helly property of some intersection graphs

    An EPG graph G is an edge-intersection graph of paths on a grid. In this doctoral thesis we will mainly explore the EPG graphs, in particular B1-EPG graphs. However, other classes of intersection graphs will be studied such as VPG, EPT and VPT graph classes, in addition to the parameters Helly …

    brazil-uerj Repository record for On the helly property of some intersection graphs (opens in a new tab)

  14. Minimal Classes of Unbounded Clique-Width

    In the study of graphs, clique-width is a parameter that has received much attention due its significance in the tractability of algorithms on certain classes of graph. Of particular interest are hereditary graph classes, those classes closed under taking induced subgraphs. A number of <i>minimal …

    the-open-u Download PDF for Minimal Classes of Unbounded Clique-Width (opens in a new tab)

  15. Complexity and algorithms related to two classes of graph problems

    … the problems associated with conversions on graphs and editing by removing a matching. We study the f-reversible processes, which are those associated with a threshold value for each vertex, and whose dynamics depends on the number of neighbors with different state for each vertex. We set a …

    brazil-uerj Repository record for Complexity and algorithms related to two classes of graph problems (opens in a new tab)

  16. Directed graph limits and directed threshold graphs

    We look at the recently developed concept of graphons first discussed by Lovász and Szegedy in 2004. These are continuous versions of adjacency matrices which arise as limits of sequences of graphs. We develop the concepts that generalize graphons to directed graphs. Several papers by Diaconis and …

    nebraska Repository record for Directed graph limits and directed threshold graphs (opens in a new tab)

Page 1 of 5