Reconstruction problems

Materials

• Graph reconstruction
  • Graph realization from Degree sequence (simple graph case). This case is solvable with the Havel-Hakimi algorithm which is a greedy recursive algorithm.
    • See also the bipartite case and directed graph case. (Not sure if they are approachable.)

• Phylogenetic tree reconstructions
  • part1
  • part2 - distance based
  • All lecture notes: all notes

Tasks

• IOI'14 Rail
• IOI'15 Towns (get partial scores)

• codeforces 329C - Graph reconstruction