Comparison among Classical,Probabilistic and Quantum Algorithms for Hamiltonian Cycle Problem

The Hamiltonian cycle problem(HCP),which is an NP-complete problem,consists of having a graph G with n nodes and m edges and finding the path that connects each node exactly once.In this paper we compare some algorithms to solve a Hamiltonian cycle problem,using different models of computations and especially the probabilistic and quantum ones.Starting from the classical probabilistic approach of random walks,we take a step to the quantum direction by involving an ad hoc designed Quantum Turing Machine(QTM),which can be a useful conceptual project tool for quantum algorithms.Introducing several constraints to the graphs,our analysis leads to not-exponential speedup improvements to the best-known algorithms.In particular,the results are based on bounded degree graphs(graphs with nodes having a maximum number of edges)and graphs with the right limited number of nodes and edges to allow them to outperform the other algorithms.

A Fault-Handling Method for the Hamiltonian Cycle in the Hypercube Topology

Many routing protocols,such as distance vector and link-state protocols are used for nding the best paths in a network.To nd the path between the source and destination nodes where every node is visited once with no repeats,Hamiltonian and Hypercube routing protocols are often used.Nonetheless,these algorithms are not designed to solve the problem of a node failure,where one or more nodes become faulty.This paper proposes an efcient modied Fault-free Hamiltonian Cycle based on the Hypercube Topology(FHCHT)to perform a connection between nodes when one or more nodes become faulty.FHCHT can be applied in a different environment to transmit data with a high-reliability connection by nding an alternative path between the source and destination nodes when some nodes fail.Moreover,a proposed Hamiltonian Near Cycle(HNC)scheme has been developed and implemented.HNC implementation results indicated that FHCHT produces alternative cycles relatively similar to a Hamiltonian Cycle for the Hypercube,complete,and random graphs.The implementation of the proposed algorithm in a Hypercube achieved a 31%and 76%reduction in cost compared to the complete and random graphs,respectively.

Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges

The k-ary n-cube Qkn （n ≥2 and k ≥3） is one of the most popular interconnection networks. In this paper, we consider the problem of a fault- free Hamiltonian cycle passing through a prescribed linear forest （i.e., pairwise vertex-disjoint paths） in the 3-ary n-cube Qn^3 with faulty edges. The following result is obtained. Let E0 （≠θ） be a linear forest and F （≠θ） be a set of faulty edges in Q3 such that E0∩ F = 0 and ｜E0｜ ＋｜F｜ ≤ 2n - 2. Then all edges of E0 lie on a Hamiltonian cycle in Qn^3- F, and the upper bound 2n - 2 is sharp.

Matchings extend to Hamiltonian cycles in hyper cubes with faulty edges

We consider the problem of existence of a Hamiltonian cycle containing a matching and avoiding some edges in an n-cubc Qn,and obtain the following results.Let n≥3,MСE(Qn),and FСE(Qn)\M with 1≤|F|≤2n-4-|M|.If M is a matching and every vertex is incident with at least two edges in the graph Qn-F,then all edges of M lie on a Hamiltonian cycle in Qn-F.Moreover,if|M|=1 or|M|==2,then the upper bound of number of faulty edges tolerated is sharp.Our results generalize the well-known result for |M|=1.

Fault-tolerant hamiltonian cycles and paths embedding into locally exchanged twisted cubes

The foundation of information society is computer interconnection network,and the key of information exchange is communication algorithm.Finding interconnection networks with simple routing algorithm and high fault-tolerant performance is the premise of realizing various communication algorithms and protocols.Nowadays,people can build complex interconnection networks by using very large scale integration(VLSI)technology.Locally exchanged twisted cubes,denoted by(s+t+1)-dimensional LeTQ_(s,t) which combines the merits of the exchanged hypercube and the locally twisted cube.It has been proved that the LeTQ_(s,t) has many excellent properties for interconnection networks,such as fewer edges,lower overhead and smaller diameter.Embeddability is an important indicator to measure the performance of interconnection networks.We mainly study the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube,LeTQ_(s,t)-(f_(v)+f_(e)),with faulty vertices f_(v) and faulty edges fe.Firstly,we prove that an LeTQ_(s,t) can tolerate up to s-1 faulty vertices and edges when embedding a Hamiltonian cycle,for s≥2,t≥3,and s≤t.Furthermore,we also prove another result that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQ_(s,t) with up to(s-2)faulty vertices and edges.That is,we show that LeTQ_(s,t) is(s-1)-Hamiltonian and(s-2)-Hamiltonian-connected.The results are proved to be optimal in this paper with at most(s-1)-fault-tolerant Hamiltonicity and(s-2)fault-tolerant Hamiltonian connectivity of LeTQ_(s,t).

Joint Energy Predication and Gathering Data in Wireless Rechargeable Sensor Network

Wireless Sensor Network(WSNs)is an infrastructure-less wireless net-work deployed in an increasing number of wireless sensors in an ad-hoc manner.As the sensor nodes could be powered using batteries,the development of WSN energy constraints is considered to be a key issue.In wireless sensor networks(WSNs),wireless mobile chargers(MCs)conquer such issues mainly,energy shortages.The proposed work is to produce an energy-efficient recharge method for Wireless Rechargeable Sensor Network(WRSN),which results in a longer lifespan of the network by reducing charging delay and maintaining the residual energy of the sensor.In this algorithm,each node gets sorted using the K-means technique,in which the data gets distributed into various clusters.The mobile charges execute a Short Hamiltonian cycle opposite direction to reach each cluster’s anchor point.The position of the anchor points is calculated based on the energy distribution using the base station.In this case,the network will act as a spare MC,so that one of the two MCs will run out of energy before reaching the BS.After the current tours of the two MCs terminate,regression analysis for energy prediction initiates,enabling the updating of anchor points in the upcoming round.Based on thefindings of the regression-based energy prediction model,the recommended algorithm could effectively refill network energy.

Rainbow Pancyclicity in a Collection of Graphs Under the Dirac-type Condition

Let G={Gi:i∈[n]} be a collection of not necessarily distinct n-vertex graphs with the same vertex set V,where G can be seen as an edge-colored(multi)graph and each Gi is the set of edges with color i.A graph F on V is called rainbow if any two edges of F come from different Gis’.We say that G is rainbow pancyclic if there is a rainbow cycle Cℓof lengthℓin G for each integerℓ2[3,n].In 2020,Joos and Kim proved a rainbow version of Dirac’s theorem:Ifδ(Gi)≥2/n for each i∈[n],then there is a rainbow Hamiltonian cycle in G.In this paper,under the same condition,we show that G is rainbow pancyclic except that n is even and G consists of n copies of Kn/2,n/2.This result supports the famous meta-conjecture posed by Bondy.

ON EDGE-HAMILTONIAN PROPERTY OF BI-CAYLEY GRAPHS

Let G be a finite group, and S be a subset of G. The bi-Cayley graph BCay（G, S） of G with respect to S is defined as the bipartite graph with vertex set G x {0,1} and edge set {（g,0）, （gs, 1）1 g ε G, s εS}. In this paper, we first provide two interesting results for edge-hamiltonian property of Cayley graphs and bi-Cayley graphs. Next, we investigate the edge^hamiltonian property of F = BCay（G, S）, and prove that F is hamiltonian if and only if F is edge-hamiltonian when F is a connected bi-Cayley graph.

Two Sufficient Conditions for Hamiltonian Graphs

Two venices of a graph are said to be c-pair if the distance between them equals to 2 and the degrees of them are both less than helf the number of the venices of the graph. This paper gives two sufficient conditions for a 3-connected or 1-tough graph to be Hamiltonian.The conditions are the generalization of the Fan-conditions in the sense that the c-pair is allowed here,but is not allowed in the Fan-conditions.

Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs

Let G = （V, E） be a complete undirected graph with vertex set V, edge set E, and edge weights I（e） satisfying the triangle inequality. The vertex set V is partitioned into clusters V1, V2 ,…, Vk. The clustered traveling salesman problem （CTSP） seeks to compute the shortest Hamiltonian tour that visits all the vertices, in which the vertices of each cluster are visited consecutively. A two-level genetic algorithm （TLGA） was developed for the problem, which favors neither intra-cluster paths nor inter-cluster paths, thus realized integrated evolutionary optimization for both levels of the CTSP. Results show that the algorithm is more effective than known algorithms. A large-scale traveling salesman problem （TSP） can be converted into a CTSP by clustering so that it can then be solved by the algorithm. Test results demonstrate that the clustering TLGA for large TSPs is more effective and efficient than the classical genetic algorithm.

Four Forbidden Subgraph Pairs for Hamiltonicity of 3-connected Graphs

For non-negative integers i,j and k, we denote the generalized net as Ni,j,k, which is a triangle with disjoint paths of length i, j and k, attached to distinct vertices of the triangle. In this paper, we prove that every 3-connected {K1,3,N8-i,i,1}-free graph is hamiltonian, where 1〈i〈4.

A Generalization of Implicit Ore-condition for Hamiltonicity of k-connected Graphs

In 2005,Flandrin et al.proved that if G is a k-connected graph of order n and V(G)=X1∪X2∪···∪Xk such that d(x)+d(y)≥n for each pair of nonadjacent vertices x,y∈Xi and each i with i=1,2,···,k,then G is hamiltonian.In order to get more sufficient conditions for hamiltonicity of graphs,Zhu,Li and Deng proposed the definitions of two kinds of implicit degree of a vertex v,denoted by id1(v)and id2(v),respectively.In this paper,we are going to prove that if G is a k-connected graph of order n and V(G)=X1∪X2∪···∪Xk such that id2(x)+id2(y)≥n for each pair of nonadjacent vertices x,y∈Xi and each i with i=1,2,···,k,then G is hamiltonian.

Novel Ω-protocols for NP

Ω-protocols, introduced by Garay, Mackenzie and Yang, is a variant of S-protocols with online extractor which is a useful tool to overcome the nest effect in concurrent scenario. In this work, we construct an Ω-protocol for Hamiltonian cycle problem, and therefore, it allows us to present Ω-protocol for any NP relation. For most general NP relations, our construction of Ω-protocols is much more efficient than the informal one described by Garay et ah and we believe that the method for our construction may be of independent interest.