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 5 of 5 for “"cactus graph"”.
-
Heuristic Algorithms For Broadcasting In Cactus Graphs
… the broadcast time of a vertex in an arbitrary graph is NP-complete. The problem is solved polynomially only for a few classes of graphs. In this thesis, we study the broadcast problem in a class of graph called a Cactus Graph. A cactus graph is a connected graph in which any two simple cycles …
-
Connections to zero forcing: Tree covers and power domination
<p>For a simple graph $G=(V,E),$ let $\mathcal{S}_+(G)$ denote the set of real positive semidefinite matrices $A=(a_{ij})$ such that $a_{ij}\neq 0$ if $\{i,j\}\in E$, $a_{ij}=0$ if $\{i,j\}\notin E$, and $a_{ii}$ is any real number. The maximum positive semidefinite nullity of $G$, denoted …
-
Approximation Algorithms for Broadcasting in Simple Graphs with Intersecting Cycles
… broadcast time of any vertex in an arbitrary graph is NP-Complete. The problem remains NP-Complete even for planar graphs of degree 3 and for a graph whose vertex set can be partitioned into a clique and an independent set. The best theoretical upper bound gives logarithmic approximation. It …
-
Analytic Methods and Combinatorial Plants
… structure named for a plant--AVL trees, cactus graphs, and sunflowers--which we refer to collectively as combinatorial plants. In our first result, we use a novel decomposition to create a succinct encoding for tree classes satisfying certain properties, extending results of Munro, …
-
Very Cost Effective Partitions in Graphs
For a graph G=(V,E) and a set of vertices S, a vertex v in S is said to be very cost effective if it is adjacent to more vertices in V -S than in S. A bipartition pi={S, V- S} is called very cost effective if both S and V- S are very cost effective sets. Not all graphs have a very cost effective …