Skip to main content
Figure 4 | BMC Bioinformatics

Figure 4

From: Multichromosomal median and halving problems under different genomic distances

Figure 4

Reduction of hamiltonian cycle in directed graph to breakpoint median for linear genomes. This figure is redrawn from [21]. Vertex a has no outgoing arc with X = A in its label set, and b has no incoming arc with A in its label set. We choose a, b such that adding arc ab to G[A] would not give a non-Hamiltonian circuit. We choose an another vertex x and insert two new vertices y and z. The incoming arcs of x in the right hand graph are the same as in the left hand graph. The outgoing arcs of z are the same as the incoming edges of x in the left hand graph. The remaining edges reduce the number of components in G[A] but leave the same number of components in G[B] and G[C].

Back to article page