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 38 for “"grid graphs"”.
-
Broadcasting in grid graphs
… In this work we consider a special kind of graphs, grids.;In 1980 A. M. Farley showed that the minimum time required to broadcast a set of M messages in any connected graph with diameter d is d + 2(M - 1). This work presents an approach to broadcasting multiple messages from the corner …
-
Liar's Domination in Grid Graphs
… P_3 x P_infty. We also give bounds for other grid graphs.
-
Paired-Domination in Grid Graphs.
… set. Determining the domination number for grid graphs is a well-known open problem in graph theory. Not surprisingly, determining the paired-domination number for grid graphs is also a difficult problem. In this thesis, we survey past research in domination, paired-domination and grid …
-
Various pushing methods on grid graphs
… thesis describes algorithms for determining if a grid of switches can be turned into all-off state from any initial configuration by various methods of activation operation (push). Among these push methods, besides the regular "+" push, "+" push with no center, "X" push, "X" push with no center, …
-
Hamiltonian Paths in Non-Rectangular Grid Graphs
… However, for some specialized types of graphs, a polynomial time solution can be found. Itai, Papadimitriou and Szwarcfiter have found that for general grid graphs the problem is NP-complete, but for rectangular grid graphs linear time is sufficient. The thesis includes a discussion of …
-
2-limited broadcast domination on grid graphs
… 2-limited broadcast domination number of various grid graphs, in particular the Cartesian products of two paths, a path and a cycle, and two cycles. The upper bounds are derived by explicit broadcast constructions for these graphs. The lower bounds are obtained via linear programming duality by …
-
The Roman Domination Problem on Grid Graphs
La Dominazione è un'area della ricerca nella teoria dei grafi in rapida evoluzione. Questa dissertazione si propone di studiare il Problema della Dominazione Romana: introdotto di recente, questo problema ha alcune interessanti applicazioni nel mondo reale, quali le strategie militari e lo studio …
-
Hamiltonian Cycle Reconfiguration in Even Staircase Grid Graphs
… 1-complex Hamiltonian cycles in a rectangular grid graph or an L-shaped grid graph. In this thesis, we give an algorithm for a Hamiltonian cycle reconfiguration problem. The algorithm transforms any 1-complex Hamiltonian cycle to any other 1 complex Hamiltonian cycle in an even staircase grid …
-
Reconfiguration of Hamiltonian cycles and paths in grid graphs
A grid graph is a finite embedded subgraph of the infinite integer grid. A solid grid graph is a grid graph without holes, i.e., each bounded face of the graph is a unit square. The reconfiguration problem for Hamiltonian cycle or path in a sold grid graph G asks the following question: given two …
-
Reconfiguration of Hamiltonian Cycles and Paths in Rectangular Grid Graphs
An m×n grid graph is the induced subgraph of the square lattice whose vertex set consists of all integer grid points {(i, j) : 0 ≤ i < m, 0 ≤ j < n}. Let H and K be Hamiltonian cycles in an m × n grid graph G. We study the problem of reconfiguring H into K using a sequence of local transformations …
-
Collaborative graph exploration
… We show for this scenario new lower bounds on grid graphs with rectangular obstacles. In addition we extends the lower bounds for these grid graphs and for trees to hold up against randomized algorithms. Furthermore we show efficient algorithms for the exploration of grid graphs as well as for …
-
Understanding Work-Efficiency of label correcting Single Source Shortest Path Algorithms - How does relaxed data structures affect the work-efficiency of parallel algorithms?
… conducted on road networks, Random Hyperbolic Graphs (RHGs), and grid graphs using several state-of-the-art relaxed priority scheduler implementations. Our results show that relaxation error is correlated with redundant work, but is not sufficient on its own to explain work-efficiency. The …
-
Global Supply Sets in Graphs
… global supply number for selected families of graphs. Also, we give bounds on the global supply number for general graphs, trees, and grid graphs.
-
On Kernels, β-graphs, and β-graph Sequences of Digraphs
… of kernels in various classes of directed graphs, most notably in oriented trees, grid graphs, and oriented cycles. The question of uniqueness of these kernels is also handled. Attention is then shifted to $\gamma$-graphs, structures associated to the minimum dominating sets of undirected …
-
Multiple message broadcasting and gossiping in the dynamically orientable graphs
… message broadcasting in dynamically orientable graphs of different network topologies. These are new problems never attempted before. Dynamically orientable graphs and six different network topologies are considered: paths, cycles, stars, binary trees, complete trees and two-dimensional grids. …
-
Algorithms for DFM in electronic design automation
… the k-colorability of rectangular and diagonal grid graphs as induced subgraphs of a rectangular or diagonal grid respectively, since it has direct applications in printing contact/via layouts. It remains an open question on how hard it is to color grid graphs due to their regularity and …
Page 1 of 2