Computer Science and Engineering Department

Southern Methodist University

Jan. 2007

Title: CSE 8355 – Graph Theory: Algorithms and Applications

Time: Tuesdays 5:00 PM – 7:50 PM

Text: Graph Theory: Haray (Amazon.com)

Introduction to Graph Theory, by Douglas B. West, Prentice-Hall

Purpose: This course will expose the student to the theory and applications of

graphs and networks. Efficient algorithms for many graph theory problems will be discussed and analyzed.

Background B.S. in Computer Science, Electrical Engineering, or Mathematics and

Required: some familiarity with graph and/or network applications. Note: Students

need not be advanced degree candidate to register as long as the prerequisites are satisfied.

Topics: Graphs, subgraphs, and networks. Trees, shortest distance trees, and

Spanning trees. Connectivity. Euler and Hamiltonian tours and the traveling salesman problem. Matchings and assignment. Graph coloring, independent sets and cliques in graphs. Planar graphs and planarity algorithms. Breadth first, depth first, and maximum adjacency search, network flows.

Project: A project will be required including a class presentation. Remote students

may provide a DVD for their presentation. The following topic areas offer particularly strong possibilities for independent projects with publication potential:

I. Trees: Development of the leaf-to-leaf paradigm for efficient solution of optimization problems on trees and acyclic networks.

II. Connectivity: Development of efficient algorithms to determine graph and subgraph connectivity. Advancements of maximum adjacency search.

III. Interval Graphs: Development of the event list data structure and the efficient determination of graph parameters for interval graphs.

IV. Random Graphs: Investigation of the chromatic number of random graphs. Extension of the expose-and-merge paradigm, and other recent topics.

V. Concurrent Flow: Investigation of maximum concurrent flow using the flow-diversion-triples formulation. Applications in computer networks and telecommunications routing. Hierarchal Maximum Concurrent flow – Sparse cuts/Hubs.

VI. Cluster Analysis: Application of graph theory and algorithms to cluster analysis. The maximum concurrent flow problem should be applicable here. HMCF

VII. Threshold Graphs: Characterizations, applications, properties of random threshold graphs.