M8160 Graph Algorithms

Faculty of Science
Autumn 2003
Extent and Intensity
2/1/0. 3 credit(s) (fasci plus compl plus > 4). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Libor Polák, CSc. (lecturer)
Guaranteed by
doc. RNDr. Libor Polák, CSc.
Department of Mathematics and Statistics – Departments – Faculty of Science
Contact Person: doc. RNDr. Libor Polák, CSc.
Timetable of Seminar Groups
M8160/01: No timetable has been entered into IS. L. Polák
Prerequisites
M5140 Graph Theory
Basics of graph theory.
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
  • Mathematics (programme PřF, M-MA, specialization Discrete Mathematics)
  • Mathematics (programme PřF, N-MA, specialization Discrete Mathematics)
Course objectives
Basic graph algorithms are discussed. The correctness is always proved, also their complexities are bounded. Students propose some further algorithms.
Syllabus
  • Elementary graph algorithms (representations of graphs, breadth-first search, depth-first search, topological sort, strongly connected components). Minimum spanning trees ( growing a minimum spanning tree, the algorithms of Kruskal and Prim). Single-source shortest paths (shortest paths and relaxation, Dijkstra's algorithm, the Bellman-Ford algorithm, single-source shortest paths in directed acyclic graphs). All-pairs shortest paths (shortest paths and matrix multiplication, the Floyd-Warshall algorithm, Johnson's algorithm for sparse graphs). Maximum flow (flow networks, the Ford-Fulkerson method, maximum bipartite matching). Data structures for graph algorithms (binary heaps, priority queues, binomial heaps, data structures for disjoint sets).
Literature
  • CORMEN, Thomas H., Charles Eric LEISERSON and Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
Assessment methods (in Czech)
Standardní přednáška, ve cvičení referují studenti řešení předem zadaných úloh.
Language of instruction
Czech
Further Comments
The course is taught annually.
Teacher's information
http://www.math.muni.cz/~polak
The course is also listed under the following terms Spring 2000, Spring 2001, Spring 2002, Spring 2003, Autumn 2004.
  • Enrolment Statistics (Autumn 2003, recent)
  • Permalink: https://is.muni.cz/course/sci/autumn2003/M8160