Algorithmic Graph Theory

Prof. Martin Golumbic

Slides and Notes of Selected Lectures (click here)

Course Description:

We present classical and more recent theory and algorithms in graph theory, in particular, related to intersection graphs and other structured families of graphs. Intersection graphs are an extremely useful model for many applications in computer science, operations research and even molecular biology, with interesting and diverse mathematical properties.

We begin by explaining and motivating the concept, and provide examples from the literature. The graph coloring problem on special families of these intersection graphs will be studied, many of which admit efficient algorithms. These techniques can be applied to scheduling classrooms or airplanes, allocating machines or personnel to jobs, or designing circuits. Rich mathematical problems also arise in the study of intersection graphs.

We will present a spectrum of research results, from simple to sophisticated, which should interest both students and professors.

Lectures will be chosen from the following list of topics.

Introduction to Intersection Graphs - [Go1, Mc21]

Review of Basic Graph Algorithms and Complexity Analysis - [Go2, CLR]

Chordal Graphs and their Applications - [Go4, Mc22]

Transitively Orderable Graphs - [Go5, Mc27.6]

Permutation Graphs - [Go7, Mc27.4]

Weakly Chordal Graphs and Strongly Chordal Graphs - [Mc27.3, Mc27.12, Go13]

Split Graphs, Threshold Graphs and CoGraphs - [Go6, Mc2 2.5, Go10 Mc25, Mc27.9]

Interval Graphs - [Go8, Mc23]

Tolerance Graphs - [GT1, GT2]

Interval Probe Graphs - [GT4, Mc23.4.1]

Intersection Graphs on Trees - [GT10, Mc22.3]

Texts:

Go: M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs,

second edition, Elsevier (2004).

Chapters 1; 2; 4(1-4, 6); 5(1,4,6-7); 6(1-2); 7(1-2,4-5); 8(1-4); 10; 13

GT: M.C. Golumbic & A.N. Trenk, Tolerance Graphs,

Cambridge University Press (2004).

Chapters 1; 2(1-3,6-7); 4(1-4,7-8)

Other references:

MP : Mahadev & Peled, Threshold Graphs and Related Topics

BLS: Brandstadt, Le & Spinrad, Graph Classes: A Survey

Mc2: T.A. McKee & F.R. McMorris, Topics in Intersection Graph Theory

Misc. papers from the literature

Students are responsible for reading all assigned material. Exercises are to be presented in class. Each student will also be expected to concentrate on a paper from the literature to be assigned in class and do a course project or presentation. The exam will be open book, covering the material discussed in the lectures.

This is a graduate elective course. Students are expected to have mastered basic undergraduate knowledge of algorithms, complexity analysis and discrete mathematics.