MATH 3330: Applied Graph Theory

Winter 2007

Dalhousie University,

Department of Mathematics and Statistics

• Assignments
• Notes and slides
• Useful links
• General Information
• Syllabus
• Calendar entry

General Information

• Lectures:

  TR 10:05-11:25

  LSC 214

• Instructor:

  Dr. J.C.M. Janssen,

  Office: Chase Building, Room 223.

  Office hours: Tuesday & Thursday 11.30-12.30, Monday 2.30-3.30
  Weekly schedule

• Course Text

  Graph Theory and its Applications,
  Jonathan L. Gross and Jay Yellen
  Second Edition, 2006, Chapman & Hall/CRC.
  ISBN 1-58488-505-X
  

Top

Useful links

Let me know if you find any other useful links (implementations of algorithms discussed in class, descriptions of interesting graph theory applications or problems, etc.), and I will add them to this list.

• The small world project
• The Oracle of Bacon
• The Erdos number project
• Comparing binaries with graph isomorphism
• Applications of Minimum Spanning Tree
• One of the first studies of the graph representing the World Wide Web. Includes data about the degree distribution and average graph distance. Uses Breadth-First Search.
• URL caching for Web crawls. This paper discusses how Web crawlers work, and how the enourmous queue containing all URLs that have not been downloaded yet can be better maintained.
• Wire routing. Java Applet which finds a path in a grid.
• BFS and DFS animation
• Visualizations of Prim's, Kruskal's and Dijkstra's algorithms.
• Another visualization of Dijkstra's algorithm. (With tutorial.)
• Application of shortest path to GIS (paper handed out in class)
• Internet routing protocol based on Dijkstra's shortest path algorithm
• archive of Dijkstra's memos (known as EWDs, or, in Dutch: EWD-tjes, pronounced "ay-way-day-chess") Dijkstra passed away in 2002.
• Java applet demonstrating the max flow algorithms
• Floyd-Warshall algorithm implemented in Javascript