Best books on algorithmic graph theory?

In summary, Arsenic 'n Lace is interested in algorithms for network research, and would like to learn more about them. He is currently reading a book on the subject, and would like to know what other algorithms or programming languages are popular among experts.
  • #1
Arsenic&Lace
533
37
I constantly find new algorithmic graph theory problems that I need to solve as I work in research. I've learned bits and pieces from google'ing and reinvented the wheel on numerous occasions but it would be nice to get a more standard background. Network science might be more applicable although I don't know; there is usually quite a bit of data on the graphs themselves which is relevant for calculations. Books on network theory/algorithmic graph theory would be nice.

Thanks,
Arsenic 'n Lace
 
Physics news on Phys.org
  • #2
Any special algorithms you're interested in? Any special programming language that you like to be used.

My favorite book on the subject is probably this free book: https://code.google.com/p/graphbook/ But if this is what you need depends a lot on what you want to do with graphs since there is so much you can do.

Some chapters are sadly unfinished though, especially the algebraic graph theory chapter is something I'm looking forward to.
 
  • #3
Looks interesting. I'm not interested in any particular algorithm, I just want to get a feel for common algorithms. I program primarily in python.

So far I've needed to work with random walks on graphs (e.g. MFPT from one cluster to another), graph clustering, metrics for quantifying network evolution, and other problems. Right at this very moment, I am examining trajectories on simple closed graphs with self edges and looking for linear algebraic techniques to quickly find certain cycles (e.g. for a 3 node network, if I have a path 0000111122222222, I want to quickly count this, and disregard a path like 1010111000110222)

EDIT: For the record, I've solved most of the above problems, but I don't know if I've reinvented the wheel, reinvented the wheel and made it worse, or reinvented the wheel and made it better (doubtful), I mainly want to see how deeply I am in unknown territory or if I just need more basic knowledge on the subject.
 
Last edited:

1. What is algorithmic graph theory?

Algorithmic graph theory is a branch of mathematics and computer science that studies the properties and algorithms of graphs, which are mathematical structures used to model relationships between objects.

2. Why is algorithmic graph theory important?

Algorithmic graph theory is important because it provides tools and techniques for solving real-world problems that involve networks, such as social networks, transportation networks, and communication networks. It also has applications in the fields of computer science, engineering, and operations research.

3. What are the key concepts in algorithmic graph theory?

Some key concepts in algorithmic graph theory include graph representation, graph traversal, shortest paths, connectivity, planarity, coloring, and matching. These concepts are used to analyze and design efficient algorithms for solving problems related to graphs.

4. What are some recommended books on algorithmic graph theory?

Some recommended books on algorithmic graph theory include "Introduction to Graph Theory" by Douglas B. West, "Algorithmic Graph Theory and Perfect Graphs" by Martin Charles Golumbic, "Networks, Crowds, and Markets: Reasoning about a Highly Connected World" by David Easley and Jon Kleinberg, "The Algorithm Design Manual" by Steven S. Skiena, and "Graph Theory and Its Applications" by Jonathan L. Gross and Jay Yellen.

5. How can one apply the knowledge from books on algorithmic graph theory?

The knowledge from books on algorithmic graph theory can be applied in various fields, such as computer programming, network analysis, data mining, and optimization. It can also be used to solve real-world problems, such as finding the shortest path between two points in a transportation network or determining the most efficient way to route information in a communication network.

Similar threads

  • Programming and Computer Science
Replies
2
Views
1K
  • Science and Math Textbooks
Replies
1
Views
2K
  • Science and Math Textbooks
Replies
1
Views
1K
  • Science and Math Textbooks
Replies
1
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
388
  • Science and Math Textbooks
Replies
4
Views
4K
  • Science and Math Textbooks
Replies
4
Views
2K
  • Science and Math Textbooks
Replies
5
Views
1K
  • Science and Math Textbooks
Replies
3
Views
3K
  • Introductory Physics Homework Help
Replies
6
Views
912
Back
Top