# 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