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"”.
-
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.
-
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 …
-
On the Bounds of the Domination Number of Permutation Graphs
No abstract prepared.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …