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

• Turnpike problem (no known solution for general case): There are n points on a line. If we are given a multiset of all distances between all pairs of point, find the location of these points. (We can assume that the point with minimum x-co-ordinate is at the origin.)
  • Graph turnpike problem (some solvable cases)

Tasks

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

• codeforces 329C - Graph reconstruction