ผลต่างระหว่างรุ่นของ "Reconstruction problems"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 8: | แถว 8: | ||
** [http://www.comp.nus.edu.sg/~bioinfo/phylogenetic%20tree%20reconstruction_2_8.pdf part2 - distance based] | ** [http://www.comp.nus.edu.sg/~bioinfo/phylogenetic%20tree%20reconstruction_2_8.pdf part2 - distance based] | ||
** All lecture notes: [http://www.comp.nus.edu.sg/~bioinfo/lecture%20notes.htm all notes] | ** All lecture notes: [http://www.comp.nus.edu.sg/~bioinfo/lecture%20notes.htm 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.) | ||
| + | ** [http://theory.stanford.edu/~tomas/turn.ps Graph turnpike problem] (some solvable cases) | ||
== Tasks == | == Tasks == | ||
รุ่นแก้ไขปัจจุบันเมื่อ 14:14, 21 มีนาคม 2559
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.)
- Graph realization from Degree sequence (simple graph case). This case is solvable with the Havel-Hakimi algorithm which is a greedy recursive algorithm.
- 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
- codeforces 329C - Graph reconstruction
