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)