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 27 for “"Perfect Graphs"”.

  1. Structural Characterisations of Hereditary Graph Classes and Algorithmic Consequences

    … 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 if the …

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

  2. Χαρακτηρισμός νέων κλάσεων τέλειων γραφημάτων και αγλόριθμοι χρωματισμού και μέγιστων διαδρομών

    … provide characterizations of two new classes of perfect graphs, namely colinear and linear graphs. Moreover, we present polynomial-time algorithms or NP-completeness results for various types of the coloring problem on graphs and polynomial-time algorithms for the longest path problem on perfect …

    greece Repository record for Χαρακτηρισμός νέων κλάσεων τέλειων γραφημάτων και αγλόριθμοι χρωματισμού και μέγιστων διαδρομών (opens in a new tab)

  3. On approximating transitivity and tractability of graphs

    … are NP-hard. But, there exists some families of graphs, called perfect graphs, where these problems become tractable. One particular class of perfect graphs are the the underlying undirected graphs of transitive digraphs- called comparability graphs. We define a new parameter β to approximate the …

    colostate Repository record for On approximating transitivity and tractability of graphs (opens in a new tab)

  4. Homogeneous sets in graphs and hypergraphs

    … of it as edges. We investigate the properties of graphs and hypergraphs in two cases of imposed restrictions on the structure of their homogeneous sets. </p> <p>First we study the asymptotic structure of random perfect graphs. We give a generation model which yields such graphs almost uniformly, …

    oxford Repository record for Homogeneous sets in graphs and hypergraphs (opens in a new tab)

  5. Αλγόριθμοι και αποτελέσματα NP-πληρότητας για προβλήματα χρωματισμού και επικάλυψης με μονοπάτια σε τέλεια γραφήματα

    … 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 results have already been published. We next …

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

  6. Vertex coloring with forbidden subgraphs

    Given a set $L$ of graphs, a graph $G$ is $L$-free if $G$ does not contain any graph in $L$ as induced subgraph. A $hole$ is an induced cycle of length at least $4$. A $hole$-$twin$ is a graph obtained by adding a vertex adjacent to three consecutive vertices in a $hole$. Hole-twins are closely …

    wilfrid-laurier Repository record for Vertex coloring with forbidden subgraphs (opens in a new tab) Download PDF for Vertex coloring with forbidden subgraphs (opens in a new tab)

  7. The computational complexity of edge colouring restricted graphs

    … complexity of edge colouring restricted graphs. Previous work has established that the chromatic index problem restricted to k­-regular graphs for any fixed k-3 remains NP-complete, whereas the problem restricted to bipartite graphs and partial k-trees for fixed k is in P. We show that …

    uvic Repository record for The computational complexity of edge colouring restricted graphs (opens in a new tab)

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

  9. Properties of (claw, 4K₁, bridge)-free graphs

    Given a set H of graphs, a graph G is H-free if it does not contain any graph in H as an induced subgraph. The complexity of the colouring problem is known when H is a set of graphs on four vertices, with three exceptions. One of those exceptions is the case of {claw, 4K1}-free graphs, for which …

    wilfrid-laurier Repository record for Properties of (claw, 4K₁, bridge)-free graphs (opens in a new tab) Download PDF for Properties of (claw, 4K₁, bridge)-free graphs (opens in a new tab)

  10. ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΤΕΛΕΙΩΝ ΓΡΑΦΗΜΑΤΩΝ

    … THEORETIC PROBLEMS, PARTICULARLY FOR PROBLEMS ON PERFECT GRAPHS. ALL ALGORITHMSARE BASED ON A NEW PRESENTATION OF THE UNDIRECTED GRAPHS. THE VERTEX SET V OF A GRAPH G=(V,E) IS PARTITIONED INTO SUBSETS, IN A SPECIFIC FASHION. WE CALL THESE SUBSETS "ADJACENCY LEVEL SETS" AND DENOTE AL(V,L), VEV, …

    greece Repository record for ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΤΕΛΕΙΩΝ ΓΡΑΦΗΜΑΤΩΝ (opens in a new tab)

  11. Edge modification on perfect and reducible graphs with application to watermarking

    … to edge modification problems on classes of graphs. For the theoretical part, we study and present polynomial algorithms for the minimum completion problem (i) of a graph with a “tail” for four subclasses of perfect graphs and (ii) of a graph and an added edge for the class of P4-sparse …

    greece Repository record for Edge modification on perfect and reducible graphs with application to watermarking (opens in a new tab)

  12. On chordal digraphs and semi-strict chordal digraphs

    Chordal graphs are an important class of perfect graphs. The beautiful theory surrounding their study varies from natural applications to elegant characterizations in terms of forbidden subgraphs, subtree representations, vertex orderings, and to linear time recognition algorithms. Haskins and Rose …

    uvic Repository record for On chordal digraphs and semi-strict chordal digraphs (opens in a new tab)

  13. Quantum independence and chromatic numbers

    … independence numbers case. Additionally, all the graphs that we studied that had known quantum parameters exhibited both the separation between the classical and quantum independence numbers and the separation between the classical and quantum chromatic numbers. This observation and the …

    waterloo Repository record for Quantum independence and chromatic numbers (opens in a new tab)

  14. Generalizations of comparability graphs

    … if there is such an assignment. Comparability graphs are a class of graphs where clique, coloring, and many other optimization problems are solved by polynomial algorithms. It also has close connections with other classes of graphs, such as interval graphs, permutation graphs, and perfect …

    colostate Repository record for Generalizations of comparability graphs (opens in a new tab)

  15. Entropy and Graphs

    … an equivalent definition for a graph to be perfect and it can also be applied to obtain lower bounds in graph covering problems. In this thesis, we review and investigate three equivalent definitions of graph entropy and its basic properties. Minimum entropy colouring of a graph was proposed …

    waterloo Repository record for Entropy and Graphs (opens in a new tab)

  16. Convex Algebraic Geometry Approaches to Graph Coloring and Stable Set Problems

    … in polynomial time the Stable Set Problem for perfect graphs. This is achieved by showing that the Stable Set Polytope of a perfect graph is the projection of a slice of a Positive Semidefinite Cone of not too large dimension. Thus, the Stable Set Problem can be solved with the use of a …

    waterloo Repository record for Convex Algebraic Geometry Approaches to Graph Coloring and Stable Set Problems (opens in a new tab)

  17. Ideal Clutters

    … on the characterization of weakly bipartite graphs; not to mention they are also the set covering analogue of perfect graphs. To matroid theorists, they are abstractions of Seymour’s sums of circuits property as well as his f-flowing property. And finally, to combinatorial optimizers, ideal …

    waterloo Repository record for Ideal Clutters (opens in a new tab)

Page 1 of 2