Compact Course: "Theory and implementation of graph theory algorithms"
2013-11-04 15:15:28
By: Information Technology Center
November 4th & 5th 2013, Phnom Penh, Cambodia
RUPP, Phnom Penh & HGS MathComp , IWR, University of Heidelberg
Organized by: IT Center and RUPP HEQCIP Project
Abstract
Graph theory is a powerful area for modeling in Scientific Computing. From communication networks to scheduling problems, these methods provide a tool to model complex interactions and derive often "good" and sometimes "optimal" solutions to these applications.
The course covers the mathematical formulation and computational implementation of several basic problems in this class such as "Traveling Salesman", "Shortest Path", "Minimal Spanning Tree", "Bipartite Matching" and "Knapsack". In exercises the discussion on implementation issues will cover the connection between solution algorithms and efficient implementations using optimal data structures. Students learn to understand complexity issues arising from different solution strategies and how to avoid bottlenecks when programming solution algorithms. The notion of "heuristics" and "decentralized algorithms" helps to distinguish several solution strategies.
Where
Room 1, Cambodia-Korea Cooperation Center (CKCC)
Schedule
| Monday, Nov 4th | |
| 09:00 – 10:30 | Lecture – Introduction to efficient algorithms |
| 10:30 – 10:45 | Break |
| 10:45 – 12:00 | Lecture – Basic problems and greedy algorithms |
| 12:00 – 14:00 | Lunch Break |
| 14:00 – 15:30 | Implementation issues for efficient algorithms |
| 15:30 – 15:45 | Break |
| 15:45 – 16:30 | Discussion: What graph theory problems arose in your research so far? |
| Tuesday, Nov 5th | |
| 09:00 – 10:30 | Lecture – From basic problems to NP-hard questions |
| 10:30 – 10:45 | Break |
| 10:45 – 11:30 | Final discussion: Lessons learned and further studies |