Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes.
John D. KececiogluDavid SankoffPublished in: CPM (1993)
Keyphrases
- approximation algorithms
- special case
- np hard
- vertex cover
- worst case
- genetic algorithm
- network design problem
- minimum cost
- set cover
- facility location problem
- constant factor
- open shop
- distance measure
- longest common subsequence
- randomized algorithms
- primal dual
- approximation schemes
- disjoint paths
- approximation ratio
- exact algorithms
- evolutionary algorithm
- np hardness
- distance function
- scheduling problem
- undirected graph
- theoretical analysis
- computational complexity