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 “"Permutation Graphs"”.

  1. Power Domination on Permutation Graphs

    … We will consider this problem as it relates to permutation graphs on cycles, and suggest upper bounds for the power domination numbers on such graphs.

    texas-state Repository record for Power Domination on Permutation Graphs (opens in a new tab)

  2. The structure of permutation graphs

    The class of permutation graphs has been studied extensively for more than two decades. The most popular representational tool employed is the permutation or matching diagram. However, the matching-diagram does not capture all the structural information of a permutation graph. The study structures …

    nebraska Repository record for The structure of permutation graphs (opens in a new tab)

  3. Algorithmic techniques for encoding permutations and permutation graphs for watermarking software, image, audio, and text

    … for encoding a watermark w into a self-inverting permutation (or, SiP for short) π*, and then embedding the self-inverting permutation π* into different digital objects, i.e., software, image, audio, and text, by using different representations of the same SiP π*. The data structures used to …

    greece Repository record for Algorithmic techniques for encoding permutations and permutation graphs for watermarking software, image, audio, and text (opens in a new tab)

  4. Related Orderings of AT-Free Graphs

    … tractable (FPT) algorithm for Cutwidth on graphs parameterized by the edge clique cover number of the graph and a new parameter, the restricted twin cover number of the graph. The restricted twin cover number of the graph generalizes the vertex cover number of a graph, and is the smallest …

    waterloo Repository record for Related Orderings of AT-Free Graphs (opens in a new tab)

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

  6. Simultaneous Graph Representation Problems

    Many graphs arising in practice can be represented in a concise and intuitive way that conveys their structure. For example: A planar graph can be represented in the plane with points for vertices and non-crossing curves for edges. An interval graph can be represented on the real line with …

    waterloo Repository record for Simultaneous Graph Representation Problems (opens in a new tab)

  7. On (in)tractability of connection and cut problems

    … to specific graph classes, such as split graphs, rooted directed path graphs, and graphs of bounded clique-width. We mainly concentrate on results that differentiate the complexity of TCP from the complexity of Steiner tree. Additionally, we analyse the computational complexity of the …

    brazil-uerj Repository record for On (in)tractability of connection and cut problems (opens in a new tab)

  8. Pseudovarieties of inverse monoids

    … Meakin showed that the set of all rooted inverse graphs (partial permutation graphs) over X is in one-to-one correspondence with the set of all closed inverse submonoids of the free inverse monoid FIM(X). In this dissertation we consider applications of inverse automata to the study of groups and …

    nebraska Repository record for Pseudovarieties of inverse monoids (opens in a new tab)

  9. A New Optimality Measure for Distance Dominating Sets

    … even when the input graph is restricted to split graphs, <em>2</em>-connected graphs, or planar bipartite graphs of degree four. In addition, the problem is in P for bounded tree-width graphs, when considering <em>k</em> as a constant, and for strongly chordal graphs, for any <em>k</em>. Then, we …

    waterloo Repository record for A New Optimality Measure for Distance Dominating Sets (opens in a new tab)

  10. Path and cycle hitting problems: algorithms and complexity

    … problems are known to be NP-complete on general graphs. It is considered unlikely that there exist polynomial-time algorithms for solving them. Motivated by the fact that many of these problems have real-world applications, researchers have been primarily focused on designing faster and faster …

    greece Repository record for Path and cycle hitting problems: algorithms and complexity (opens in a new tab)