Jump to content

User talk:David Eppstein/Graph Algorithms

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Goals

[edit]

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)[reply]

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).

Justin W Smith talk/stalk 20:10, 12 July 2010 (UTC)[reply]

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)[reply]
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)[reply]

Omissions

[edit]

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)[reply]

Another note to myself

[edit]

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

David Eppstein (talk) 06:56, 27 August 2012 (UTC)[reply]