8
$\begingroup$

I am looking for a reference text on applied graph theory and graph algorithms. Is there a standard text used in most computer science programs? If not, what are the most respected texts in the field? I have Cormen et al.

$\endgroup$
  • $\begingroup$ In what applications are you interested? Algorithmic applications? $\endgroup$ – A.Schulz Jul 21 '12 at 6:20
  • $\begingroup$ I am interested in directed graphs, but want a definitive text, if such a thing exists. I thought (hoped) that there might be a dedicated text that covered theory, history, and applications. Thanks for replying. $\endgroup$ – JEHR Jul 22 '12 at 1:57
  • 3
    $\begingroup$ Searching Amazon for "applied graph theory" yields numerous results. I suggest you start there (or a similar search elsewhere), go to your library and look into the most promising candidates. Buy the one you find most accessible resp. fitting your needs. Not every book helps everybody, that's a very person-specific matter. $\endgroup$ – Raphael Jul 23 '12 at 7:14
  • 1
    $\begingroup$ I searched Amazon before asking here. I though that would be obvious. Thus, I came here to see if there was a definitive text for the topic that is widely used in CS programs (see my original question). $\endgroup$ – JEHR Jul 23 '12 at 12:22
  • 1
    $\begingroup$ In my experience, a "definitive text" hardly ever exists, and more so in computer science (a young field). Different books cater to different audiences and different preferences both in terms of content selection and presentation. $\endgroup$ – Raphael Jul 26 '12 at 5:58
3
$\begingroup$

For digraphs in particular, there's Band-Jensen & Gutin's "Digraphs: Theory, Algorithms and Applications". It covers quite a bit of material.

The first edition is free to download now that the second edition is out (There's a link to the pdf on their page). Of course if you've got access to a Springerlink account, you can get the second edition instead!

Apart from being free, while I'm not sure of its popularity (especially considering it's "relatively" young), it's a weighty tome, with extensive coverage from basics to quite advanced topics and from both practical and theoretical perspectives.

The other advantage is that it's one of the few (perhaps only?) full coverage texts specifically on digraphs, rather than a being a general graph theory book with material on digraphs.

$\endgroup$
  • $\begingroup$ Thanks! Free is always very good. Looks like it covers my main interest (directed graphs) quite well! $\endgroup$ – JEHR Jul 26 '12 at 12:58
  • 3
    $\begingroup$ In light of an ongoing discussion on Meta, I'd encourage you to try to improve this answer by providing evidence that this text, in particular, is your recommendation. What evidence do you have to suggest that it is popular, or widely used? What evidence do you have that it is respected? Note that there is no policy, yet, on "list questions", but I am personally (not officially) curious to see how much justification people can provide. $\endgroup$ – Patrick87 Jul 26 '12 at 15:05
  • $\begingroup$ Luke, I have done a limited review of the book you suggested and it is the best book on directed graphs that I have seen. At 700+ pages it is quite hefty. Just reading the intro and looking at the topics I can tell this is what I have been looking for-- and, its free!! At my stage of learning, this is sufficiently definitive for my needs. It will take me a year to get through this. Thanks for a great suggestion. $\endgroup$ – JEHR Jul 26 '12 at 17:43
5
$\begingroup$

I would take a look at the free book by Bondy and Murty: Graph Theory with Applications. This book is less-algorithmic and more graph-theoretical than other resources recommended here. There is also a newer version of the book, which is not available for free on the net, but is extremely well-written and with updated notation. In comparison to other free books on graph theory (as for example Diestel), Bondy/Murty uses a less formal approach to prove and explain the theory.

The reason I have used it, is because it is the primary text-book in the course on Graph Theory at The Technical University of Denmark, lectured by Carsten Thomassen, in which I have been assistant teacher for 2 years.

$\endgroup$
  • $\begingroup$ Wow, another free text that looks pretty good! Thanks for this great suggestion! $\endgroup$ – JEHR Jul 26 '12 at 13:04
  • 2
    $\begingroup$ In light of an ongoing discussion on Meta, I'd encourage you to try to improve this answer by providing evidence that this text, in particular, is your recommendation. What evidence do you have to suggest that it is popular, or widely used? What evidence do you have that it is respected? Note that there is no policy, yet, on "list questions", but I am personally (not officially) curious to see how much justification people can provide. $\endgroup$ – Patrick87 Jul 26 '12 at 15:05
  • $\begingroup$ I have updated my answer with some justification. $\endgroup$ – utdiscant Jul 27 '12 at 5:17
3
$\begingroup$

There is always the free Algorithmic Graph Theory which covers graph algorithms, data structures, traversals, and several other topics. If it doesn't have what you're looking for, at least you're not out anything.

$\endgroup$
  • $\begingroup$ Thanks, I have never heard of this before. I'll add it to my library. It appears there is no one, definitive text that is widely used, so this may be a good find. $\endgroup$ – JEHR Jul 23 '12 at 12:22
  • $\begingroup$ Many thanks, for this pointer. I wasn't aware of this book. It looks very nice and has lot of exercises! And it is free! $\endgroup$ – A.Schulz Jul 25 '12 at 15:48
  • 1
    $\begingroup$ In light of an ongoing discussion on Meta, I'd encourage you to try to improve this answer by providing evidence that this text, in particular, is your recommendation. What evidence do you have to suggest that it is popular, or widely used? What evidence do you have that it is respected? Note that there is no policy, yet, on "list questions", but I am personally (not officially) curious to see how much justification people can provide. $\endgroup$ – Patrick87 Jul 26 '12 at 15:05
3
$\begingroup$

Have a look at (the non free) Algorithmic Graph Theory by Alan Gibbons. It's an oldie but quite widely used in CS, it has a computational approach but does also cover the theory. At around 250 pages it's not too intimidating and is well respected.

$\endgroup$
  • 2
    $\begingroup$ In light of an ongoing discussion on Meta, I'd encourage you to try to improve this answer by providing evidence that this text, in particular, is your recommendation. What evidence do you have to suggest that it is popular, or widely used? What evidence do you have that it is respected? Note that there is no policy, yet, on "list questions", but I am personally (not officially) curious to see how much justification people can provide. $\endgroup$ – Patrick87 Jul 26 '12 at 15:05
2
$\begingroup$

There is the book "Managing and Mining Graph Data" from Charu C. Aggarwal.

It contains (among others):

  • Graph Mining: Laws and Generators
  • Graph Data Management and Mining
  • Graph Indexing
  • Graph Reachability Queries
  • Graph Matching
  • Graph Classification

As the title suggests it concentrates on graph data and algorithms for this type of data. I don't know if this is what you are searching for, but I can really recommend this book:

Managing and Mining Graph Data

EDIT: Since one comment asked for "evidence" for the relevance of my answer, I would like to point out the following:

  • Charu Aggarwal is one of the guiding lights in the field of Data Mining (Top 20 Authors).
  • The book is very well written and easy to understand, even with little previous knowledge.
  • There is a review of this book from the ACM stating a recommodation of reading it.
  • And finally: I like it :D
$\endgroup$
  • 2
    $\begingroup$ In light of an ongoing discussion on Meta, I'd encourage you to try to improve this answer by providing evidence that this text, in particular, is your recommendation. What evidence do you have to suggest that it is popular, or widely used? What evidence do you have that it is respected? Note that there is no policy, yet, on "list questions", but I am personally (not officially) curious to see how much justification people can provide. $\endgroup$ – Patrick87 Jul 26 '12 at 15:05
  • $\begingroup$ I hope I could clarify, why I think this book is relevant. $\endgroup$ – user2025 Jul 26 '12 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.