Hamiltonian path analysis of viral genomes [PDF]
Nature Communications, 2018 Cryo-electron microscopy (EM) is undergoing a revolution, enabling the study of viral pathogens in unprecedented detail. The asymmetric EM reconstruction of bacteriophage MS2 at medium resolution (8.7 A) by Koning et al.1, and the subsequent ...
Reidun Twarock +2 more
doaj +9 more sources
An Image Encryption Algorithm Based on Random Hamiltonian Path [PDF]
Entropy, 2020 In graph theory, Hamiltonian path refers to the path that visits each vertex exactly once. In this paper, we designed a method to generate random Hamiltonian path within digital images, which is equivalent to permutation in image encryption.
Wei Zhang +4 more
doaj +3 more sources
Beyond the Fröhlich Hamiltonian: Path-integral treatment of large polarons in anharmonic solids [PDF]
Physical review B, 2021 The properties of an electron in a typical solid are modified by the interaction with the crystal ions, leading to the formation of a quasiparticle: the polaron.
Matthew Houtput, J. Tempere
openalex +3 more sources
Spectral Conditions for Graphs to be k-Hamiltonian or k-Path-Coverable
Discussiones Mathematicae Graph Theory, 2020 A graph G is k-Hamiltonian if for all X ⊂ V (G) with |X| ≤ k, the subgraph induced by V (G) \ X is Hamiltonian. A graph G is k-path-coverable if V (G) can be covered by k or fewer vertex disjoint paths.
Liu Weijun +3 more
doaj +2 more sources
On Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2014 Graph ...
Christian Löwenstein +2 more
doaj +2 more sources
Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs [PDF]
International Symposium on Algorithms and Computation, 2009 In this paper we study the problem of existence of a crossing-free acyclic hamiltonian path completion (for short, HP-completion) set for embedded upward planar digraphs.
Tamara Mchedlidze, Antonios Symvonis
openalex +2 more sources
Solving a Hamiltonian Path Problem with a bacterial computer
Journal of Biological Engineering, 2009 Background The Hamiltonian Path Problem asks whether there is a route in a directed graph from a beginning node to an ending node, visiting each node exactly once. The Hamiltonian Path Problem is NP complete, achieving surprising computational complexity
Treece Jessica +18 more
doaj +2 more sources
2-generated Cayley digraphs on nilpotent groups have hamiltonian paths [PDF]
, 2011 Suppose G is a nilpotent, finite group. We show that if {a,b} is any 2-element generating set of G, then the corresponding Cayley digraph Cay(G;a,b) has a hamiltonian path.
Morris, Dave Witte
core +5 more sources
Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number [PDF]
arXiv.org, 2023 A Hamiltonian path (a Hamiltonian cycle) in a graph is a path (a cycle, respectively) that traverses all of its vertices. The problems of deciding their existence in an input graph are well-known to be NP-complete, in fact, they belong to the first ...
Nikola Jedličková, Jan Kratochv'il
semanticscholar +1 more source
Finding Hamiltonian and Longest (s,t)-Paths of C-Shaped Supergrid Graphs in Linear Time
Algorithms, 2022 A graph is called Hamiltonian connected if it contains a Hamiltonian path between any two distinct vertices. In the past, we proved the Hamiltonian path and cycle problems for general supergrid graphs to be NP-complete.
Fatemeh Keshavarz-Kohjerdi, Ruo-Wei Hung
doaj +1 more source