ผลต่างระหว่างรุ่นของ "Reconstruction problems"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 4 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 1: | แถว 1: | ||
| + | == Materials == | ||
| + | * Graph reconstruction | ||
| + | ** [https://en.wikipedia.org/wiki/Graph_realization_problem Graph realization] from [http://mathworld.wolfram.com/DegreeSequence.html Degree sequence] (simple graph case). This case is solvable with the [https://en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm Havel-Hakimi algorithm] which is a greedy recursive algorithm. | ||
| + | *** See also the [https://en.wikipedia.org/wiki/Bipartite_realization_problem bipartite case] and [https://en.wikipedia.org/wiki/Digraph_realization_problem directed graph case]. (Not sure if they are approachable.) | ||
| + | |||
* Phylogenetic tree reconstructions | * Phylogenetic tree reconstructions | ||
** [http://www.comp.nus.edu.sg/~bioinfo/phylogenetic%20tree%20reconstruction_1_7.pdf part1] | ** [http://www.comp.nus.edu.sg/~bioinfo/phylogenetic%20tree%20reconstruction_1_7.pdf part1] | ||
** [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 == | ||
| + | |||
| + | * IOI'14 [http://www.ioinformatics.org/locations/ioi14/contest/day1/rail/rail.pdf Rail] | ||
| + | * IOI'15 [http://ioi2015.kz/content/view/1/271 Towns] (get partial scores) | ||
| + | |||
| + | * [http://codeforces.com/problemset/problem/329/C codeforces 329C] - Graph reconstruction | ||
รุ่นแก้ไขปัจจุบันเมื่อ 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
