Melvin's digital garden


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

Links to this note