User talk:David Eppstein/Graph Algorithms

Goals

This is intended to cover graph algorithms at an upper-division undergraduate level, for students already familiar with the design and analysis of algorithms. I used a similar grouping of topics to the Spring 2010 offering of ICS 163 at UC Irvine, which I taught primarily from Wikipedia articles rather than from a text; however, I have not (yet?) included the motivating applications from that offering, and I included some additional topics to allow for some choice as well as the possibility of stretching the course to semester length. —David Eppstein (talk) 03:52, 12 July 2010 (UTC)

This is a very nice selection of articles. It includes a few topics with which I'm only superficially familiar. There were a few topics that I did not see in the list, but thought might be of value. No book can be exhaustive, so there might be good reason to not include some of these (even if only in the interest of concision).

• Selected topics from Algebraic graph theory
  • Eigenvalue, eigenvector and eigenspace
  • Laplacian matrix
  • The Matrix-tree theorem.
  • Characteristic polynomial
• Crossing number (graph theory)
• Facility location For this, I was actually thinking of the k-center problem. This and the others were topics covered in a "Graph Algorithms" course that I took a couple years ago. 20:42, 12 July 2010 (UTC)
• Steiner tree problem There are several variations of the "Steiner Tree" problem. The one I'm thinking of is a true generalization of MST, i.e., a minimum spanning tree connecting some given subset of the vertices. 20:14, 12 July 2010 (UTC)

Justin W Smith ^talk/_stalk 20:10, 12 July 2010 (UTC)

Thanks for the suggestions. Some discussion of algebraic methods would definitely be a good idea and would allow bringing in PageRank as an application. I thought about including Steiner trees in the MST chapter but eventually decided against it because the existing Steiner tree article has almost nothing about graphs or algorithms. —David Eppstein (talk) 20:20, 12 July 2010 (UTC)

And closely related to PageRank are Markov chains, which have a multitude of applications. Being discrete, Markov chains have a nice graph theoretic interpretation. Justin W Smith ^talk/_stalk 20:37, 12 July 2010 (UTC)

Omissions

A (most likely itself incomplete) list of some subjects that are not yet covered well in this material:

• Algebraic methods (per above discussion)
• Dynamic graph algorithms
• K shortest paths
• Spanners and approximate shortest path data structures
• Network design problems (maybe because I don't tend to find them very interesting)
• Random graphs (generation of random graphs e.g. Erdos-Renyi, Barabasi, ERGM, as well as methods that use random graphs)
• Fixed parameter tractability (there's some coverage, especially in the covering/packing chapter, but not very thorough

—David Eppstein (talk) 16:53, 15 July 2010 (UTC)

Another note to myself

Aside from topics that just aren't here, the articles that are currently linked but are in the worst shape are:

• Shortest path problem
• Longest path problem
• Single-linkage clustering
• Maze generation algorithm
• Bipartite graph
• Assignment problem
• Closure problem
• Fraysseix–Rosenstiehl's planarity criterion

—David Eppstein (talk) 06:56, 27 August 2012 (UTC)