alexa A Method to Select the Edges in the Minimum Hamiltonian Cycle | Open Access Journals
ISSN: 0974-7230
Journal of Computer Science & Systems Biology
Like us on:
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on
Medical, Pharma, Engineering, Science, Technology and Business

A Method to Select the Edges in the Minimum Hamiltonian Cycle

Yong Wang*

School of Renewable Energy, North China Electric Power University, China

*Corresponding Author:
Yong Wang
School of Renewable Energy
North China Electric Power University
No.2, Beinong Road, Hui Longguan
Changping, Beijing, 102206, China
Tel: 8582280970
E-mail: [email protected]

Received Date: June 26, 2015; Accepted Date: August 05, 2015; Published Date: August 07, 2015

Citation: Wang Y (2015) A Method to Select the Edges in the Minimum Hamiltonian Cycle. J Comput Sci Syst Biol 08:249-254. doi:10.4172/jcsb.1000197

Copyright: © 2015 Wang Y. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Visit for more related articles at Journal of Computer Science & Systems Biology

Abstract

To find the minimum Hamiltonian cycle is the objective of traveling salesman problem (TSP) whereas it has been proven to be NP-complete. To select the right edges in the minimum Hamiltonian cycle, the frequency graph is computed with a set of optimal i-vertex paths. The number of optimal i-vertex paths is formulated according to i. In these frequency graphs, the frequencies of the edges in the minimum Hamiltonian cycle are generally bigger than the average frequency and those of most of the other edges. Before i ≤ n/2+1 for even number n and i ≤ (n ± 1)/2+1 for odd number n, the frequencies of the edges in the minimum Hamiltonian cycle increase faster than the average frequency does according to i. The frequencies on the edges and their change can be taken as the heuristic information to select the edges in the minimum Hamiltonian cycle. Two simple examples are given to show the change of the frequencies of the edges in the minimum Hamiltonian cycle. The results show that they are different from those of the other edges according to i. The results can be used as the basis to design algorithms for TSP

Keywords

Traveling salesman problem; Minimum Hamiltonian cycle; Frequency graph; Optimal i-vertex path

Introduction

The goal of traveling salesman problem (TSP) is to find the minimum Hamiltonian cycle (Min-HC) i.e., a cycle that visits each city once and exactly once and incurs the least length, time or cost, etc. It has been proven to be NP-complete [1]. There is no exact polynomial algorithm for TSP until NP=P. Till now the classical time complexity of TSP is believed as O*(2n). TSP has been extensively studied in the fields of combinatorial optimization and computer science due to its theoretical and practical values [2].

In mathematics, an undirected weighted graph (WG) is used to represent the symmetrical TSP. For a WG with n vertices, it is noted as G={V, E, W}, where V={v1, v2,…, vn} are the vertex sets, E=[eij]n × n are the edges and W=[wij]n × n are the weights of edges, vi (1 ≤ i ≤ n) is the vertex, eij(1 ≤ i, j ≤ n) is the edge linking the vertices vi and vj and wij is the weight of eij. For the symmetrical TSP, wij=wji. A cycle visiting each vertex once and exactly once is called a Hamiltonian cycle (HC) and the Min-HC is the HC with the minimum weights, i.e., optimal Hamiltonian cycle.

Given an undirected WG with n vertices, the number of the HCs is (n-1)1/2. It is impossible to find the Min-HC by evaluating each of them. The exact algorithms have been designed by many researchers to deal with TSP. The graph search algorithms [3] are feasible for TSP with less than tens of cities. Considering more constraints, the integer programming [4,5] and dynamic programming methods [6] can resolve the TSP with thousands of cities on super computers. For larger scale of TSP, the computation time is too long. It is reported that a large scale of TSP with 85,900 has been resolved with Concorde package [6]. A 128 networked computers system is used to execute the task and 1.2 years was consumed. The computation time is equal to 136 years when one computer completes the computation task. To resolve more complex TSP cases, the new methods are advocated to reduce the computation time.

The hardness of TSP results from a large number of HCs whereas the number of Min-HCs is usually very small. Generally, we strive to find one Min-HC. With a WG, the edges in the Min-HC are hard to discriminate in view of their weights. In most cases, not all the small weighted edges are included in the Min-HC. The method to determine the edges in the Min-HC is valuable. Most scholars design the exact algorithms to search the edges, paths in the Min-HC until the Min-HC is found [7-9]. The results show that the exact polynomial algorithm does not exist until NP=P. The heuristics based on the weights usually search the approximations [10-12]. Different from above research, the frequency graph is introduced and used to determine the possible edges in the Min-HC. The frequency graph is computed with a set of optimal i-vertex paths and it includes the law of conversion between the optimal i-vertex paths and the Min-HC. In other words, the frequencies of the edges in the Min-HC are generally bigger than those of most of the other edges. Hence, only the edges with big frequencies above a threshold will be taken as the candidate edges in the Min-HC. The threshold is changed according to number i. When the optimal i-vertex paths are short, the frequencies of a few edges in the Min-HC will not be outstanding. If i is big enough, the frequencies of all the edges in the Min-HC will be much bigger than those of the other edges and the Min-HC is easy to find. The frequency graph has been introduced in a previous paper [13]. However, the change of the frequencies of the edges in the Min-HC is not discussed. In this paper, we use mathematical methods to reveal two characteristics of the frequencies of the edges in the Min-HC. Firstly, the frequencies of the edges in the Min-HC are generally bigger than the average frequency and those of most of the other edges in a given frequency graph. In addition, the frequencies of the edges in the Min-HC increase faster than the average frequency does according to i. Here the frequency graphs are computed with different set of optimal i-vertex paths (the change of the frequencies of the edges in the Min-HC will be shown with a series of frequency graphs). The edges with these characteristics are used to compose the Min-HC. The findings can be as the basis to design algorithms for TSP.

The Frequency Graph (Fg) and its Function

The relationships between the optimal i-vertex paths and the Min-HC are described first. Given a WG with n vertices, an HC is the sequence of all of the vertices and it is represented as HC=(v1, v2, …, vn-1, vn, v1). Each HC is combined with a set of paths named as i-vertex paths (Pi) (2 ≤ i ≤ n). The P with i vertices is represented as Pi=(v1, v2, …, vi-1, vi). The superscript i indicates the number of vertices in the Pi. It has two end vertices v1 and vi and the other vertices are the middle vertices. Similarly, the Min-HC includes the same number of Pis. It notes that the Pis in the Min-HC are different from most of the other Pis. The Pis in the MIN-HC are named as the optimal i-vertex paths (OPi). As the Min-HC, an optimal i-vertex path does not change short whatever the middle vertices are exchanged. An optimal i-vertex path with i vertices is noted as OPi=(v1, v2, …, vi-1, vi). In particular, OP2=P2=(v1, v2) represents an edge.

Given an OPi in the MIN-HC, its two end vertices are concluded. In addition, the OPi is shorter than that of the other Pis with the same vertices in condition that their two end vertices are identical. With the description of the optimal i-vertex paths, the number of OPis is computed as formula (1) [13] for symmetrical TSP.

Equation (1)

Where Cin is the number of the combinations in case that i vertices are selected from n vertices. The number of OPis rises first if i ≤ n/2+1 for even number n or i ≤ (n ± 1)/2+1 for odd number n and then decreases according to i. There is a maximal number when i=n/2+1 for even number n (i=(n ± 1)/2+1 for odd number n). The ratio between the number of OPi+1s and OPis is computed as formula (2).

Equation (2)

In view of formula (2), the number of OPis reaches its maximum when i is less than or equal to (n+1)/2. It is interesting that the ratio ri is related to the Harmonic Progression. The partial sum of ri is computed as formula (3).

Equation (3)

Where ln is the sign of the nature logarithm and γ is the Euler constant.

The number of Pis is Pin/ 2 , where Pin is the number of the permutations in case that i vertices are selected from n vertices. It always increases until i=n. The Pis is classified into OPis and non-OPis (NOP) whose number is equal to Pin/2-i× (i-1) ×Cin/2. It is clear that the number of NOPis is much bigger than that of the OPis once i is bigger than 4. As we know, none of these NOPis belong to the Min-HC. These NOPis are useless to search the Min-HC. When we design algorithms for TSP, the NOPis should be neglected in the search process.

Only n OPis belong to the Min-HC and the other i×(i-1)×Cin/2 - nOPis cannot if only one Min-HC is taken into account. In addition, the OPjs with more vertices are combined with the OPis (i<j) with fewer vertices. Similarly, none of the NOPis will belong to an arbitrary OPj. Given all of the OPjs, the OPis emulated from the OPjs are the intersections between the OPis and the OPjs. These OPis have the potential to form the longer OPjs even the Min-HC. On the other hand, these OPis not in the OPjs have no chance to form the longer OPjs and the Min-HC. If a set of OPjs with more vertices are given, the frequencies of the OPis can be emulated from them. The OPis with bigger frequencies are included by more number of OPjs and they are apt to belong to the Min-HC. In the extreme case, an OPis included by all of the OPjs must belong to the Min-HC. Certainly, its frequency is maximal. In addition, the nearer the set of OPjs approach to the Min- HC, the bigger the frequencies of the OPis in the Min-HC will be. The nearness represents the number of intersections between the OPjs and the Min-HC, i.e., the number of OPis emulated from the set of OPjs. On the other hand, the OPis with small or zero frequencies have little change to compose the Min-HC.

The Min-HC is combined with the edges and the frequencies of edges are concerned. Given a set of OPis with more than 2 vertices, the frequencies of the edges are emulated and an FG is computed. The FG has the similar topological structure as the WG. In an FG, the numbers on the edges are their frequencies emulated from the set of OPjs. For TSP, the FGs in which the frequencies of the edges in the Min-HC are much bigger than those of the other edges are regarded. Then the edges in the Min-HC will be easily selected from these FGs.

When all of the OPis are used to compute an FG, the average frequency of the edges is computed as formula (4) in case that the FG includes all of the edges.

Equation (4)

It notes that the average frequency changes as a combinatorial number according to i. In fact, the frequencies of the edges have big distinctions when the FG is computed with the OPis. Though the number of optimal i-vertex paths increases first and then decreases, the number of edges they include may become less and less according to i. The frequencies of some edges will be much bigger than those of the other edges because they are included in many long OPis. In reverse, some edges are seldom able to compose the long OPis and their frequencies will be small or zero. For each edge in the Min-HC, at least i-1 OPis include it based on its different positions in these OPis. These i-1 OPis are used to compose the OP2i-2s in the Min-HC. For example in Figure 1, the edge (vi, vj) will be included by 3 OP4s, 4 OP5s, 5 OP6s and etc.

computer-science-systems-biology-Min-HC

Figure 1: The number of OPis with the edge (vi, vj) in the Min-HC.

Even if no other OPis include the edges in the Min-HC, the frequencies of the edges in the Min-HC will be no less than i-1. Furthermore, the edges in the Min-HC have more potential than the other edges to compose the long OPis because all the OPis approach to the Min-HC according to i until they become the OPns. Among the n × (n-1)/2 OPns, n OPns turn into the Min-HC when their two end vertices are connected. Therefore, the edges in the Min-HC have more chance to compose the OPis than the other edges do, especially to compose the long OPis. Their frequencies changes as formula (4) and they will be bigger than the average frequency in most cases. On the other hand, the frequencies of most of the other edges will be much smaller than the average frequency when i is big enough. That’s their difference. The intrinsic reason is that they cannot compose the long OPis near to the Min-HC. The edges with big frequencies are included by many OPis and they have the potential to form the Min-HC. In the extreme case, the edges included by all of the OPis have the biggest frequencies and they belong to the Min-HC. Hence, we take the edges with big frequencies as the candidate edges in the Min-HC.

The Changes of the Frequencies of the Edges in the Min-Hc

Given an FG computed with a set of OPis and it includes K edges (K>n), the formula (5) is given as follows. Where fO represents the frequency of an arbitrary edge in the Min-HC and fR is the average frequency of the rest K-1 edges, f is the average frequency of the K edges.

Equation (5)

It believes that fO is bigger than f and f is bigger than fR (it is right in most cases). When K is near to n × (n-1)/2, fO-f will be much bigger than f-fR. It says fO is much bigger than f whereas fR is near to f. In an ideal case, each of the OPis includes the edge in the Min-HC and fO is almost equal to formula (1). fR is computed as formula (6) as K=n × (n-1)/2.

Equation (6)

It is more close to formula (4) and they have a big gap with the maximum value of fO (see formula (1)).

There is the other special case that fO is equal to f. For example, fO=f if i=2 and 3. When i=2 and 3, the fO is equal to 1 and 2 × (n-2), respectively. As we know, the number of OPis are always becoming bigger according to i until i is bigger than n/2+1 for even number n ((n+1)/2+1 for odd number n). Some of the other edges have less and less chance to compose the OPis according to i. Their frequencies will increase slower than the average frequency does. On the other hand, the edges in the Min-HC have more and more possibility to compose the long OPis. Therefore, fO will be bigger than f in most cases according to i.

The readers wonder fO may be smaller than f in some FGs. How can we discriminate the edges in the Min-HC? In addition, there will be a lot of the other edges with frequencies bigger than f, which will enhance the difficulty to select the right edges in the Min-HC. From above analysis, the edges in the Min-HC will have more chance to compose the OPis according to i than most of the other edges do. It is easy to infer that the frequencies of the edges in the Min-HC increase faster than the average does according to i. The edges in the Min-HC can be selected with respect to their frequency changes. Given two sets of OPi+1s and OPis, the change of the average frequency is computed as formula (7).

Equation (7)

Formula (7) illustrates the change between two average frequencies computed with the OPi+1s and OPis. The change of the frequencies of the edges in the Min-HC will be bigger than that computed with formula (7) for most of OPis. We can compute a series of FGs with the corresponding OPis and then find the edges whose frequencies become faster than the average frequency does according to i. These edges with these characteristics are taken as the candidate edges in the Min-HC.

When i become big, it is hard to compute the OPis with many vertices. In addition, the minimum frequency of the Min-HC edges is concerned to be as the threshold to select the right edges. In a recent research [14], the frequencies of edges are computed with the frequency polygons with i vertices. Given a TSP with n vertices (cities), it includes Cin weighted polygons with i vertices. In each of the i-vertex weighted polygons, there are i × (i-1)/2 edges. Hence, every edge is included in Ci-2n-2 i-vertex weighted polygons. In each i-vertex weighted polygon, there exist i × (i-1)/2 OPis with i-1 edges. A frequency polygon is computed with these i × (i-1)/2 OPis. The frequency graph computed with the frequency polygons is the same as that computed with the OPis. In an i-vertex frequency polygon, the frequencies of edges are nearly determined. In addition, the number of edges in the i-vertex frequency polygons is less than that of the weighted polygons because the frequency of some edges is zero. The number of edges in an i-vertex weighted polygon is derived as (2 +ε )(i − 2) , where ε ≤ 1 . For large scale of TSP and i=n, the number of edges in the frequency graph is nearly equal to 2n. For small number i, the number of edges in the i-vertex frequency polygons is taken as ai, where a ≤ 3. The average frequency of the edges in an i-vertex frequency polygon is computed as (i-1)2/2a. The frequency of the Min-HC edges is bigger than the average frequency according to i. They are close to or bigger than (i-1)2/2a in each of the i-vertex frequency polygons. Hence, the minimum frequency of the Min-HC edge is given as formula (8).

Equation

Examples and Discussion

A simple Euclidean example with 10 vertices is used to give an overview of the method. The vertices are noted with numbers {0,1,2,3,4,5,6,7,8,9} and their corresponding coordinates are shown in Table 1. The Min-HC is (0,3,5,4,9,8,7,6,2,1,0).

Vertex No. 0 1 2 3 4 5 6 7 8 9
Coordinates 82,7 91,38 83,46 71,44 64,60 68,58 83,69 87,76 74,78 71,71

Table 1: The vertices’ No. and their corresponding coordinates.

Due to the simplicity of the example, all of the OPis (4 ≤ i ≤ 10) are generated to compute 10 FGs. Each FG is computed with the OPis with the same number of vertices. The frequencies of the 10 edges in the Min-HC are recorded according to i. The changes of the frequencies of these edges are lined according to i and shown in Figure 2. The horizontal axis represents the number i, which means the FG is computed with the OPis. The vertical axis means the frequencies of the edges (in the Min-HC). The bottom bold line is the change of the average frequency computed with formula (4). It notes that when i is big enough, the FG will include smaller and smaller number of edges. The formula (4) should be modified. When i=8, 9, 10 in this example,the number of edges in the FGs are 43, 38 and 25, respectively. The average frequencies are computed with the concrete number of edges but not with the 45.

computer-science-systems-biology-changes-frequencies

Figure 2: The changes of the frequencies of the 10 edges in the Min-HC according to i.

In view of Figure 2, the frequencies of the edges in the Min-HC are bigger than the average frequency in most cases. The frequencies of the edge (6,2) are always the minimum comparing with those of the other edges. It is smaller than the average frequency when i=4. Except i=4, the frequencies of all of the edges are always bigger than the average frequency. In addition, the frequencies of these edges are much bigger than the average frequency after i>4. It says the edges in the Min-HC have more chance to compose the OPis than most of the other edges do according to i. That is to say, the edges in the Min-HC are apt to form the OPis near to Min-HC.

The minimum frequency of the Min-HC edge is given according to i in Table 2. The parameter a is computed in view of formula (8). It is found the parameter a is smaller than 3. In most cases, the parameter a is near to 2 and the minimum frequency of the Min-HC edge is approximately equal to Equation

i 4 5 6 7 8 9 10
Min. 82 227 395 455 323 125 20
Ci-2n-2 84 224 350 336 205 76 18
a 1.54 1.97 2.21 2.94 2.12 2.04 2.02

Table 2: The minimum frequency of the Min-HC edge according to i (Example 1).

On the other hand, the frequencies of most of the other edges will not always be bigger than the average frequency according to i, especially when i is big. The edges with small frequencies are seldom included by the OPis and they have little chance to compose the long OPis and the Min-HC. Among the other 35 edges, 10 edges whose frequencies are the maximum when i=4 are chosen to illustrate their frequencies according to i. The changes of the frequencies of these edges are shown in Figure 3. The average frequency is also given with bold lines for comparisons. They are different from the change of the frequencies of the Min-HC edges. Before i ≤ 5, the frequencies of these edges are bigger than the average frequency. After i>5, the frequencies of some edges begin to become smaller than the average frequency. When i=6, 7, 8, 9 and 10, the frequencies of 2, 3, 5, 10 and 10 edges are smaller than the average frequency, respectively. The frequencies of the rest 25 edges are smaller than the average frequency after i>5 and they are smaller than those of the edges shown in Figure 3. They are impossible to compose the Min-HC.

computer-science-systems-biology-changes-frequencies

Figure 3: The changes of the frequencies of the other 10 edges according to i.

Although the frequencies of some other edges are bigger than those of a few Min-HC edges when i is small, their changes have obvious distinctions according to i. The frequencies of the edges in the Min-HC will become bigger than the average frequency whereas those of most of the other edges will be smaller than the average frequency once i is big.

Come back to formula (1), the number of OPis reaches the maximum when i=n/2+1 for even number n. In theory, the frequencies of the edges emulated from the OPis will rise before i ≤ n/2+1. After i>n/2+1, their frequencies will decrease owing to the reduction of the OPis. The average frequency just conforms to the rule. For the simple example, the average frequency computed with OP7s is smaller than that computed with OP6s. The frequencies of the edges will be the maximum when i=6. Before i=6, the frequencies of the edges in Figures 2 and 3 increase more rapidly than the average frequency does (the frequencies of the OHC increases faster than the other edges). However, it is interesting that the frequencies of the edges in the Min-HC still arise until i=7. It means the Min-HC edges have more chance to compose the long OPis than the other edges do according to i. See Figure 2, the frequencies of the Min-HC edges becomes bigger and bigger until i=7. After that, the frequencies of them are still much bigger than the average frequency. It is different from the change of the frequencies of the other edges. In Figure 3, the frequencies of the other edges and the average frequency begin to decrease when i>6. In addition, the frequencies of the other edges decrease more rapidly than the average frequency does until they become smaller than the average frequency. It is the second difference between the frequencies of the edges in the Min-HC and those of the other edges.

When i is smaller than n/2+1 (n is even), the frequencies of the edges rise according to i. When i=n/2+2 for even number n, the frequencies of the edges in the Min-HC will still rise whereas those of the other edges will begin to decrease.

Figures 2 and 3 give us an overview of the changes of the frequencies of the edges according to i when n is even. Next the other simple example is adopted to illustrate the changes of the frequencies of the edges if n is odd. The first 9 vertices in Table 1 are selected to compute all of the OPis (4 ≤ i ≤ 9) and then 9 FGs are computed with these OPis. The Min-HC is (0,1,2,6,7,8,4,5,3,0). The changes of the frequencies of the 9 edges in the Min-HC are shown in Figure 4. The average frequency is drawn with bold lines in Figure 4. When i=8 and 9, the FG includes 31 and 21 edges, respectively. They are similar to those in Figure 2. Only two frequencies of edge (2, 6) are smaller than the average frequency when i=4 and 5. All of the frequencies of the other edges are bigger than the average frequency according to i. The minimum frequency of the Min-HC edge is listed in Table 3 according to i. The parameter a is also computed with formula (8). Similarly, parameter a is below 3 according to i. It says the number of edges in the frequency polygons is less than 3i according to i.

i 4 5 6 7 8 9
Min. 61 139 192 169 83 17
Ci-2n-2 21 35 35 21 7 1
a 1.55 2.01 2.27 2.24 2.07 1.88

Table 3: The minimum frequency of the Min-HC edge according to i (Example 2).

computer-science-systems-biology-changes-frequencies

Figure 4: The changes of the frequencies of the 9 edges in the Min-HC according to i.

The other 9 edges with the maximum frequencies when i=4 are chosen and their frequency changes are shown in Figure 5 according to i. Different from the changes of the frequencies in Figure 4, some of these frequencies are bigger than the average frequency first and then become smaller than the average frequency according to i.

computer-science-systems-biology-changes-frequencies

Figure 5: The changes of the frequencies of the other 9 edges according to i.

The number of OPis reaches the maximum value when i=(n ± 1)/2+1 for odd number n. In this case, the number of OP5s and OP6s is the maximum. In theory, the frequencies of the edges will be the maximum when i=6. Figure 4 shows the frequencies of the Min-HC edges reach their maximum number when i=6 and then decreases

The changes are different from those in Figure 2 where they reach the maximum number when i=7(i=n/2+2). Before i=6, the frequencies of the Min-HC edges increase sharply in Figure 4. However, the frequencies of the other edges increase slower from i=5 to i=6 in Figure 5. This is a big difference of Figures 4 and 5. Although the frequencies of some other edges increases before i=(n+1)/2+1 for odd number n, the frequencies of the Min-HC edges increase faster than the other edges do from i=(n-1)/2+1 to i=(n+1)/2+1. For the frequencies of the Min-HC edges, they increase sharply to reach their maximum before i=(n+1)/2+1. On the other hand, the frequencies of the other edges rise a little slower from i=(n-1)/2+1 to i=(n+1)/2+1 than they before act. It verifies that the edges in the Min-HC have more possibility to compose the long OPis than the other edges do according to i.

Some useful conclusions are drawn according to the experiments with the two simple examples. When an FG is computed with the OPis, the frequencies of the edges in the Min-HC will be bigger than that computed with formula (4) in most cases. When i becomes big, the formula (8) is more suitable to compute the minimum frequency of the Min-HC edge. The frequencies of the Min-HC edges become bigger and bigger until they reach the maximum frequencies. In this stage, they increase faster than the average frequency does according to i. When i is big, they are much bigger than the average frequency and those of most of the other edges. Moreover, the frequencies of the edges in the Min-HC will still arise when i=n/2+2 for even number n. For odd number n from i=(n-1)/2+1 to i=(n+1)/2+1, the frequencies of the edges in the Min-HC increase as before whereas those of the other edges will increase more slowly than before. After i>n/2+2 for even number n and i>(n+1)/2+1 for odd number n, the frequencies of the edges in the Min-HC will be much bigger than the average frequency according to i. On the other hand, the frequencies of most of the other edges decrease faster than the average frequency does until they become smaller than the average frequency.

Conclusion and Future Work

The revelation of the change of the frequencies of the Min- HC edges is the main contribution of the research. The Min-HC is combined with n OPis but not the NOPis whereas it is hard to conclude which OPis belong to the Min-HC. When these OPis are converted into the FGs, the difference between the Min-HC edges and the other edges is illuminated by their frequencies. When the FGs are computed with the OPis, the edges in the Min-HC usually have bigger frequencies than those of the other edges. The intrinsic reason is that these OPis approach to the Min-HC nearer and nearer according to i. The edges in the Min-HC have more chance to compose the OPis than that the other edges, especially to combine the long OPis. Hence, the edges with big frequencies emulated from them have the potential to compose the Min-HC.

In general, the frequencies of the edges in the Min-HC are bigger than the average frequency and they will be much bigger than the average frequency when i is big. The formula (8) can be used to approximate the minimum frequency of the Min-HC edge. The frequencies of the edges in the Min-HC increase faster than the average frequency does according to i if i<n/2+1 for even number n and i<(n+1)/2+1 for odd number n. In the two simple examples, it is observed that the frequencies of the Min-HC edges will still become bigger when i=n/2+2 for even number n. On the other hand, the frequencies of the other edges begin to decrease once i>n/2+1. For odd number n from i=(n-1)/2+1 to i=(n+1)/2+1, the frequencies of the edges in the Min- HC increase as before whereas those of the other edges will increase more slowly than before. The results mean the Min-HC edges have more possibility to compose the long OPis than the other edges do. The future work will focus on the minimum frequency of the edges in the Min-HC. We will verify if the minimum frequency is bigger than a given number in the worst case.

Acknowledgements

The authors acknowledge the funds supported by Fundamental Research Funds for the Central Universities (Grant No. 2015ZD10) and the NSFC (Grant No.51205129).

References

Select your language of interest to view the total content in your interested language
Post your comment

Share This Article

Relevant Topics

Article Usage

  • Total views: 11722
  • [From(publication date):
    September-2015 - Nov 18, 2017]
  • Breakdown by view type
  • HTML page views : 7935
  • PDF downloads : 3787
 

Post your comment

captcha   Reload  Can't read the image? click here to refresh

Peer Reviewed Journals
 
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals
International Conferences 2017-18
 
Meet Inspiring Speakers and Experts at our 3000+ Global Annual Meetings

Contact Us

Agri & Aquaculture Journals

Dr. Krish

[email protected]

1-702-714-7001Extn: 9040

Biochemistry Journals

Datta A

[email protected]

1-702-714-7001Extn: 9037

Business & Management Journals

Ronald

[email protected]

1-702-714-7001Extn: 9042

Chemistry Journals

Gabriel Shaw

[email protected]

1-702-714-7001Extn: 9040

Clinical Journals

Datta A

[email protected]

1-702-714-7001Extn: 9037

Engineering Journals

James Franklin

[email protected]

1-702-714-7001Extn: 9042

Food & Nutrition Journals

Katie Wilson

[email protected]

1-702-714-7001Extn: 9042

General Science

Andrea Jason

[email protected]

1-702-714-7001Extn: 9043

Genetics & Molecular Biology Journals

Anna Melissa

[email protected]

1-702-714-7001Extn: 9006

Immunology & Microbiology Journals

David Gorantl

[email protected]

1-702-714-7001Extn: 9014

Materials Science Journals

Rachle Green

[email protected]

1-702-714-7001Extn: 9039

Nursing & Health Care Journals

Stephanie Skinner

[email protected]

1-702-714-7001Extn: 9039

Medical Journals

Nimmi Anna

[email protected]

1-702-714-7001Extn: 9038

Neuroscience & Psychology Journals

Nathan T

[email protected]

1-702-714-7001Extn: 9041

Pharmaceutical Sciences Journals

Ann Jose

[email protected]

1-702-714-7001Extn: 9007

Social & Political Science Journals

Steve Harry

[email protected]

1-702-714-7001Extn: 9042

 
© 2008- 2017 OMICS International - Open Access Publisher. Best viewed in Mozilla Firefox | Google Chrome | Above IE 7.0 version
adwords