Xu2008

CREATED: 200810200729 Title: A Fast and Exact Algorithm for the Median of Three Problem—A Graph Decomposition Approach

\[\sum_{i \in G} D = \sum_{i \in G} N - \sum_{i \in G} C\]

• minimizing \(\sum D\) = maximizing \(\sum C\)
• multiple breakpoint graph, adjacencies = perfect matching
• n = #genes, r = #extant genomes
• median graph, add new node q to represent median
• adequate subgraphs to decompose MBG G
• H, G - H can be solved separately by finding optimal matching in H and G-H
• simple adequate subgraph
• ASMedian
  • upper/lower bound on #cycles
  • decompose MBG recursively using inventory of 16 simple adequate subgraphs