NDLTD logo NDLTD Union Catalog and Global ETD Search

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

  1. Hamiltonian cycle and related problems : vertex-breaking, grid graphs, and Rubik's Cubes

    Rudoy, MikhailMassachusetts Institute of Technology2017

    … complexity of several problems related to the Hamiltonian Cycle problem. We begin by introducing a new problem, which we call Tree-Residue Vertex-Breaking (TRVB). Given a multigraph G some of whose vertices are marked "breakable," TRVB asks whether it is possible to convert G into a tree via a …

    mit Repository record

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

    Ascigil, Mehmet

    … 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

  3. Finding Hamiltonian Cycles

    Kaminanai, Srihder

    <p>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

  4. Topics in Stochastic Combinatorial Optimization and Extremal Graph Theory

    Kaul, HemanshuUniversity of Illinois at Urbana-Champaign2015

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

    uiuc Repository record

  5. Linear-time algorithms for graphs with bounded branchwidth

    Christian, William Anderson, JrRice University2003

    … INDEPENDENT SET, M AXIMUM CUT, GRAPH COLORING, HAMILTONIAN CYCLE, and DISJOINT PATHS). The linearity is achieved assuming the provision of a branch decomposition of the instance graph. We then modify the framework to create a multithreaded framework that uses the existing problem-specific …

    rice Repository record

  6. On 4-Regular Planar Hamiltonian Graphs

    High, David

    … as a 4-regular planar graph. The existence of a Hamiltonian cycle in such a graph is necessary in order to use the graph to compute an upper bound on rope length for a given knot. The algorithm to generate such graphs is discussed and an exact count of the number of graphs is obtained. In order …

    wku-diss Repository record

  7. Precise Partitions Of Large Graphs

    Salehi Nowbandegani, Pouria2014

    … Lemma, we extend some known results about cycles of many lengths to include a specified edge on the cycles. The results in this chapter will help us in rest of this thesis. In 2000, Enomoto and Ota posed a conjecture on the existence of path decomposition of graphs with fixed start vertices …

    gsu Repository record

  8. Combinatorial optimization using quantum computing

    Oppong, Gloria2026

    … Problem (TSP), which aims to find a minimum-cost Hamiltonian cycle visiting each city exactly once. Using Qiskit, we implement the Quantum Approximate Optimization Algorithm (QAOA) on both simulators and quantum hardware, and compare its performance with that of classical exact optimization via …

    utc Repository record

  9. Fault-tolerance embedding of rings and arrays in star and pancake graphs

    Gajjala, Ramesh Reddy

    … In this thesis, we present methods to embed Hamiltonian paths (H-path) and Hamiltonian cycles (H-cycle) in a star graph {dollar}S\sb{n}{dollar} and pancake graph {dollar}P\sb{n}{dollar} in a faulty environment. Such embeddings are important for solving computational problems, formulated for …

    unlv Repository record

  10. Planar Graphs and their Duals on Cylinder Surfaces

    Auer, ChristopherUniversität Passau

    … the deque characterizes planar graphs with a Hamiltonian path. This result extends the known characterization of planar graphs with a Hamiltonian cycle by two stacks. By these insights, we also obtain a new characterization of queue graphs and their duals. We also consider the complexity of …

    passau-thes Repository record

  11. Topics in the Generation of Ideals of Posets

    Powers, Mackenzie WilliamCarleton University2025

    … between vertices that differ by a swap, has a Hamiltonian path. The conjecture is true for series-parallel posets and interval orders. We prove the conjecture also holds for the fence posets, but that the conjecture is false for the 3-ideals of the crown poset with six elements. We also provide …

    carleton Repository record

  12. Cayley graphs of order 6pq are Hamiltonian

    Maghsoudi, Farzad, University of Lethbridge. Faculty of Arts and Science2020

    lethbridge

  13. Hamiltonian cycles through specified edges in bipartite graphs, domination game, and the game of revolutionaries and spies

    Zamani Nasab, RezaUniversity of Illinois at Urbana-Champaign2011

    Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-07-10T16:04:32Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 thesis.pdf: 580482 bytes, checksum: 33853047e47046b466c6e010e8cbbd38 (MD5) Zamani Nasab_Reza.pdf: 580482 bytes, checksum: …

    uiuc Repository record

  14. Modeling and Optimization of Rechargeable Sensor Networks

    Xie, LiguangVirginia Tech2013

    … We introduce the concept of renewable energy cycle and offer both necessary and sufficient conditions for a sensor node to maintain its renewable energy cycle. We study an optimization problem, with the objective of maximizing the ratio of the WCV's vacation time over the cycle time. For this …

    vt Repository record