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 58 for “"Hamiltonian cycle"”.

  1. Finding a Second Hamiltonian cycle in Barnette Graphs

    … of an oik, and (2) finding a second Hamiltonian cycle in cubic graphs. The existence of solution for both problems is guaranteed by a parity argument. For the first problem we prove that deciding whether a 2-oik has a room-partitioning is NP-hard, even if the 2-oik corresponds to a …

    waterloo Repository record for Finding a Second Hamiltonian cycle in Barnette Graphs (opens in a new tab)

  2. Hamiltonian Cycle Reconfiguration in Even Staircase Grid Graphs

    … combinatorial optimization, etc. The problem of Hamiltonian cycle reconfiguration has been studied for various graph classes. And the valid changes are maintaining the Hamiltonicity after each intermediate steps. Some previous results show linear time reconfiguration algorithm for 1-complex …

    brock Repository record for Hamiltonian Cycle Reconfiguration in Even Staircase Grid Graphs (opens in a new tab)

  3. Hamiltonian cycle problem, Markov decision processes and graph spectra

    The Hamiltonian cycle problem (HCP) can be succinctly stated as: "Given a graph, find a cycle that passes through every single vertex exactly once, or determine that this cannot be achieved". Such a cycle is called a Hamiltonian cycle. The HCP is a special case of the better known Travelling …

    adelaide Repository record for Hamiltonian cycle problem, Markov decision processes and graph spectra (opens in a new tab)

  4. An Algorithm to Generate 4-Regular Planar Hamiltonian Graphs

    … problem of randomly generating 4-regular planar Hamiltonian graphs is discussed and a solution is described. An algorithm which efficiently generates the graphs in linear time and in a near-uniform manner is given. In addition, a formula is provided that determines the total number of such …

    wku-diss Repository record for An Algorithm to Generate 4-Regular Planar Hamiltonian Graphs (opens in a new tab)

  5. Reconfiguration of Hamiltonian Cycles and Paths in Rectangular Grid Graphs

    … {(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 called moves. A box of G is a unit square face. A box with vertices a, b, c, d is switchable in H if exactly two of …

    york Repository record for Reconfiguration of Hamiltonian Cycles and Paths in Rectangular Grid Graphs (opens in a new tab)

  6. Hamiltonian cycles and the space of discounted occupational measures

    … Measures (DOM) was developed for the Hamiltonian Cycle Problem (HCP). In this thesis, we exploit geometric properties of extreme points of that polytope. In particular, we refine the feasible region induced by that polytope into a narrower one. We show that the problem of finding a …

    adelaide Repository record for Hamiltonian cycles and the space of discounted occupational measures (opens in a new tab)

  7. Finding Hamiltonian Cycles

    Finding a Hamiltonian cycle in a graph is used for solving major problems in areas such as graph theory, computer networks, and algorithm design. In this thesis various approaches of Hamiltonian cycle algorithms such as backtrack algorithms and heuristic algorithms, their basic ideas, and their …

    wku-diss Repository record for Finding Hamiltonian Cycles (opens in a new tab)

  8. Hamiltono ciklo ieškojimas kvantiniais skaičiavimais /

    The Hamiltonian cycle search problem is one of the most well-known problems in graph theory, and is relevant in many areas such as computer graphics, network routing, and many others. The Hamiltonian cycle problem belongs to the class of NP-complete problems, so that in the general case the …

    vilnius Repository record for Hamiltono ciklo ieškojimas kvantiniais skaičiavimais / (opens in a new tab)

  9. Reconfiguration of Hamiltonian cycles and paths in grid graphs

    … a unit square. The reconfiguration problem for Hamiltonian cycle or path in a sold grid graph G asks the following question: given two Hamiltonian cycles (or paths) of G, can we transform one cycle (or path) to the other using some "operation" such that we get a Hamiltonian cycle (or path) of G …

    uvic Repository record for Reconfiguration of Hamiltonian cycles and paths in grid graphs (opens in a new tab)

  10. Polygon reconstruction from visibility information

    … of this thesis extracts, in o(E) time, the Hamiltonian cycle that corresponds to the boundary of the polygon from the polygon's ordered visibility graph. Also, it converts an unordered visibility graph and Hamiltonian cycle to the ordered visibility graph for that polygon in O(E) time. The …

    lethbridge Repository record for Polygon reconstruction from visibility information (opens in a new tab)

  11. Hamiltonicity, Pancyclicity, and Cycle Extendability in Graphs

    … which guarantee the existence of long cycles. Long cycles have roles in applications to civil engineering, chemistry, and communications, among many others, but the problem, in and of itself, of determining whether a graph has a cycle of some fixed and typically large length is one of …

    utahstate Repository record for Hamiltonicity, Pancyclicity, and Cycle Extendability in Graphs (opens in a new tab)

  12. Routing and broadcasting in two-dimensional linear congruential graphs of degree four

    … LC graphs of degree 4 in which f1 generates a Hamiltonian cycle, and f2 generates a few disjoint cycles."

    concordia Download PDF for Routing and broadcasting in two-dimensional linear congruential graphs of degree four (opens in a new tab)

  13. Cayley graphs of order 6pq are Hamiltonian

    … S be a generating set of G. We prove there is a Hamiltonian cycle in the corresponding Cayley graph on G with connecting set S.

    lethbridge Repository record for Cayley graphs of order 6pq are Hamiltonian (opens in a new tab)

  14. Topics in Stochastic Combinatorial Optimization and Extremal Graph Theory

    … w.h.p. this random geometric graph contains a Hamiltonian cycle if it is 2-connected.

    uiuc Repository record for Topics in Stochastic Combinatorial Optimization and Extremal Graph Theory (opens in a new tab)

  15. Tutte paths and even covers

    … literature due to their applications towards the Hamiltonian cycle problem. We prove the existence of Tutte paths in which the number of components is bounded for circuit graphs, a natural family of planar graphs which generalizes 3-connected planar graphs. As a consequence, we obtain a sharp …

    gatech Repository record for Tutte paths and even covers (opens in a new tab)

  16. Optimal selection of operators in genetic algorithm for tsp /

    The Travelling Salesman Problem aims to discover Hamiltonian cycle route through the cities positioned on a two-dimensional space. This optimization problem presents a traditional challenge for which different solution methods apply. The article examines the genetic solution method based on natural …

    vilnius Repository record for Optimal selection of operators in genetic algorithm for tsp / (opens in a new tab)

  17. Planar and hamiltonian cover graphs

    … product of posets whose cover graphs have hamiltonian cycles that parse into symmetric chains. Posets of height two can have arbitrarily large dimension. In 1981, Kelly provided an infinite sequence of planar posets that shows that the dimension of planar posets can also be arbitrarily …

    gatech Repository record for Planar and hamiltonian cover graphs (opens in a new tab)

Page 1 of 3