Advanced Graph Algorithms (Summer 2012)

Basic Information

Lecture time:	Monday 12:15-14:00 / Thursday 16:15-18:00 (lecture on April 30th is in the MMCI-building, Room 323)
Lecture room:	Room 023 (E1.4)
Lecturers:	Ran Duan, Jens M. Schmidt and Magnus Wahlström
Tutorial time:	Wednesday 08:30-10:00, except on May 2nd, which is from 10-12
Tutorial room:	Room 023 (E1.4), except on April 25th, which is in the Rotunda 3rd Floor E1.4 and on May 2nd, which is in Room 022 (E1.4).
Tutors:	Bernhard Schommer

Description

This course covers advanced graph algorithms from various fields. We give also a graph-theoretic background for the problems that need it. Submission of weekly exercise solutions is due on Monday 12:00; at least 50% of the total points are necessary to be admitted to the written exam at the end of the term.

Lectures

Date	Block	Topic	Lecturer	Homework	Scribe Notes	References
Apr 16	Basics	Introduction, Machine Model, Graph Data Structures, Bipartite Graphs, Eulerian Graphs	Jens		Notes01 N. Jasper	[1][2]
Apr 19	Basics	Circuits & Trails, Fleury's Algorithm, Hierholzer's Algorithm	Jens	hw01	Notes02 B. Nyári	[W1][W2][1]
Apr 23	Connectivity	Top. Sort, Detecting Strong Components, 2-Connectivity / 2-Edge-Connectivity	Jens		Notes03 M. Narang	[3][1]
Apr 26	Connectivity	(Open) Ear Decompositions, Strong Orientations, Testing 2-(Edge-)Connectivity in Linear Time, Bipolar Orientations, s-t-Numberings + Algorithm	Jens	hw02	Notes04	[4][5][2]
Apr 30	Matchings	Definitions, Hopcroft–Karp algorithm, Edmonds algorithm	Ran (room change)		Slides05
May 3	Matchings	Hall's Theorem, Hungarian Method for Bipartite Weighted Matchings	Ran		Slides06
May 7	Matchings	Weighted Matchings in General Graphs, Some approximate approach	Ran	hw03	Slides07
May 10	Dynamic Algorithms	Dynamic Connectivity and Spanning Trees in Amortized Poly-log time	Ran		Slides08	[6]
May 14	Dynamic Algorithms	Dynamic Connectivity in Worst-case O(n½) time	Ran		Slides09	[7][8][9]
May 17		No lecture (Ascension Day)
May 21	Planar Graphs	Planar Separator Theorem and its Applications	Ran	hw04	Slides10	[10]
May 24	Planar Graphs	Embeddings (combinatorial+planar), Euler's Formula, Detour to Platonic Solids, Kuratowski's Theorem, Dual Graphs, Interdigitating Trees	Jens	hw05
May 28		No lecture (Pentecost Day)
May 31	Planar Graphs	Quad-Edge Data Structure, s-t-plane Graphs, Vertex Adjacency, How to 5-Color a Planar Graph	Jens
June 4	Planar Graphs	Max-Cut in polynomial time	Jens	hw06
June 7		No lecture (Corpus Christi)
June 11	Planar Graphs	Minimum Spanning Trees in linear time for H-minor-free graphs and in time O(m log log n) for general graphs	Jens
June 14		Shortest Paths with Matrix Multiplication	Ran	hw07
June 18	NP-Hard Problems	FPT problems, Colorcoding (k-paths), Iterated Compression (FVS)	Magnus
June 21	NP-Hard Problems	Kernel for Feedback Vertex Set	Magnus	hw08
June 25	NP-Hard Problems	Kernel for Vertex Cover (via Matchings)	Magnus (room change)			room: MMCI building, R323
June 28	NP-Hard Problems	FP-Algorithm for Multiway-Cut, "Important" Separators	Magnus	hw09
July 2	NP-Hard Problems	FP-Algorithm for Planar Dominating Set	Magnus
July 5	NP-Hard Problems	Treewidth	Magnus	hw10
July 9		tbd	Magnus
July 12		tbd	Ran	hw11
July 16	Research Talk	Planarity Testing in Linear Time via Certificates for 3-Connected Graphs	Jens
July 19	Research Talk	tbd	Ran
July 23	Research Talk	tbd	Magnus
July 26		Exam	all

Prerequisites:	Basics in discrete mathematics, calculus, algorithms and complexity. At Saarland University these topics are covered in the bachelor courses Mathematik für Informatiker 1, Grundzüge der Theoretischen Informatik, and Grundzüge von Algorithmen und Datenstrukturen.
Policies:	SWS: 4+2, Credit Points: 9
Exam:	To be admitted to the exam, you have to achieve at least 50% of the total number of points in the tutorials. Your grade will only be dependent on the exam, which takes place on 26.07. 14:00 in room 021, MPI-building.

[1]	J. A. Bondy and U. S. R. Murty. Graph Theory. Springer, 2008
[2]	R. Diestel. Graph Theory. Springer, 2012. (Free preview available online)
[3]	I. Wegener. A simplified correctness proof for a well-known algorithm computing strongly connected components. Inf. Process. Lett. 83:1, pp. 17-19, 2002.
[4]	J. M. Schmidt. A Simple Test on 2-Vertex- and 2-Edge-Connectivity. Manuscript.
[5]	U. Brandes. Eager st-Ordering, ESA'02, pp. 247-256, 2002.
[6]	J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723–760, 2001.
[7]	G. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14(4), 781–798 (1985)
[8]	D. Eppstein, Z. Galil, G. Italiano, A. Nissenzweig. Sparsification – a technique for speeding up dynamic graph algorithms. J. ACM 44(5), 669–696 (1997)
[9]	T. M. Chan, M. Patrascu, and L. Roditty. Dynamic connectivity: Connecting to networks and geometry. In Proceedings 49th FOCS, pages 95–104, 2008.
[10]	R. Lipton, and R. Tarjan. A separator theorem for planar graphs. SIAM J. APPL. MATH., Vol. 36, No. 2, pages 177–189, 1979.

More Courses of the Algorithms and Complexity Group