Irena Penev
Topics in Structural Graph Theory and Algorithms - NDMI105 (winter 2019/2020)
Time and place
Course content
Chordal graphs and Lexicographic Breadth-First-Search (LexBFS). Clique-cutsets and algorithmic applications. Universally signable graphs. Detecting odd holes (and recognition of perfect graphs). Trigraphs.
|
Tentative schedule of lectures
|
Weeks 1-2. Chordal graphs & Lexicographic Breadth-First-Search (LexBFS).
Week 3-4. Clique-cutsets and algorithmic applications.
Weeks 5-6. Universally signable graphs.
Weeks 7-9. Detecting odd holes.
Weeks 10-11. Trigraphs.
Weeks 12-14. TBD
|
Literature
Lecture notes and journal articles, including the following:
|
M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl, "Detecting an odd hole", arXiv:1903.00208.
M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, "Universally signable graphs", Combinatorica 17 (1) (1997), 67-77.
M. Milanič, I. Penev, and N. Trotignon, "Stable sets in {ISK4,wheel}-free graphs", Algorithmica, 80(2) (2018), 415-447.
D.J. Rose, R.E. Tarjan, and G.S. Lueker, "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing 5 (1976), 266-283.
R. Tarjan, "Decomposition by clique separators", Discrete Mathematics 55 (1985), 221-232.
|
|
Evaluation
The final grade will be based on a 90 minute presentation of one research paper.
|
|