Link collection Graph Algorithms

General / Basics

• Introductionary sources:

• Graphs from Mathworld [Mathworld]: a brief definition with examples
• Graph Theory [Wikipedia Encyclopedia]: definitions in graph theory
• Graphs and Algorithms [Webpearls principles and practice of Mathmatics] : a general website explains most of the famous graph theory concepts
• Design and analysis of Algorithms [University of Texas at Arlington]: a whole university course discussing nearly everything concerning graphs and algorithms
• Graphs [Rochester Institute of Technology]: explanation of the basic concepts about graphs, breadth-first search, depth-first search, and many other basic problems (good for beginners)
• Review of Elementary Graph Theory [Boost.org]: good site for beginners explaining all the basic concepts of graph theory

• Advanced sources:

• Advanced Topics in Graph Algorithms [Tel Aviv University]: a wide site about GA, basic knowledge is required
• Journal of Graph Algorithms and Applications[Brown University]: journal about graphs
• GOBLIN: A Graph Object Library for Network Programming Problems [Universitaet Augsburg] : a C++ library implementing nearly every thing about graphs
• Graph Algorithms [Heriot Watt University]: introducing a graph abstract data type with suggestions for implementing the most famous algorithms.
• LINK [Rutgers, The State University of New Jersey]: software package programmed in C++, very helpful in graph research.
• Other Maths [Private Website]: discusses various mathematical problems with examples and further material.
• The LEDA User Manual [Algorithmicsolutions.info]: LEDA stands for Library of Efficient Data types and Algorithms a C++ library containing all of the important algorithms, implemented in an efficient way.
• The Boost Graph Library (BGL) [Boost.org]: another try to implement graphs in C++, this time from Boost.org.

• Supplementary useful sources:

• Data Structures [Sussex University]: starts from the basic data structures like arrays, stacks,... and continues till graphs and their algorithms.
• Dictionary of Algorithms and Data Structures [National institute of standards and technology]: a dictionary for the vocabulary of graph theory.
• Win-Prolog Goodies [Private Webpage]: implementations in Prolog for most of the combinatorial algorithms including TSP and many others.
• The Stony Brook Algorithm Repository [Stoony Brook University New York]: a very big website containing useful theoretical definitions and implementations in many languages like: C++, C, Java, Fortran, and others.

• Applets and Animations:

• Graph Algorithms Animations [Algorithm Animation Tool ANIMAL]: animation of many algorithms like BFS, DFS, Dijkstra shortest path algorithm, and others.
• Graph Algorithms Applet [University of California Berkeley]: a compact applet for creating and editing graphs.

Traveling Salesman Problem (TSP)

• Introductionary sources:

• Das mathematische Problem des Handlungsreisenden [ZVW Online]: a definition with some information from a mathematical point of view about the Traveling-Salesman-Problem (in German).
• Introduction to TSP [University of Magdeburg]: a brief introduction to the TSP including many useful Applets.
• Informatik-Wettbewerb an der Fachhochschule Bonn-Rhein-Sieg [Fachhochschule Bonn-Rhein-Sieg] : gives a good introduction for beginners, and shows many methods of solving the TSP including very useful information about Branch-and-Bound (in German).
• Traveling Salesman Problem [Mathworld]: a short definition from Mathworld with examples and related links.

• Applets and Animations:

• Das Problem des Handlungsreisenden [Gymnasium Zitadelle]: includes the source code of a full TSP applet in Java (in German).
• Das Travelling Salesman Problem [University of Freiburg] (in German)
• Insertion methods for Travelling Salesman [University of Western Australia]
• Projekt TSP [Fachhochschule Regensburg] (in German)
• Touropt Applet (simple heuristics) [Stockheim.net]
• Travelling Salesman [Katholische Universitaet Eichstaett]
• Travelling Salesman Problem [Private webpage]
• Anwendung: Das Travelling Salesman Problem [University Ulm]: an essay explains the methods of genetic algorithms in solving the TSP (in German).
• Solving the Travelling Salesman Problems Using Genetic Algorithms [Ai-depot.com] : a very clear simplified explanation of the use of genetic algorthims in solving the TSP.
• Das bipartite Travelling-Salesman-Problem [Christian-Albrechts-University zu Kiel]: explaining the bipartite TSP problem, Efficient approximation Algorithms, and the asymmetric bipartite TSP (in German).
• Links to the TSP homepage [Princeton University]: a huge collection of links contains everything about the TSP.
• Neil Simonetti's TSP page [Cornegie Mellon]: a collection of dynamic programming sources to solve the TSP, also contains a lot of links.
• Solving TSPs [Princeton University]: a collection of links concerning how to solve the TSP -needs some background knowledge-.

• Hamiltonian Cycle:

• Hamiltonian Circuit from Mathworld [Mathworld]: a brief definition with examples.
• Hamiltonian cycle problem [Wikipedia Encyclopedia]: a definition with examples, literature and third party links.
• The Hamiltonian Page [Private Webpage]: a big list of papers and third party links about Hamiltonian Cycle & Path problems.

Routing Problems

• A Survey of Arc Routing Problems [University of Heidelberg]: a very detailed discussion of nearly all the routing problems including literature and links.
• Gruppenunterricht zum Thema Routing-Algorithmen [Eidgenössische Technische Hochschule Zürich]: a complete report about routing alogrithms from an engineering point of view (in German)
• Planning Algorithms [University of Illinois]: a complete website about planning algorithms, from the definition to the complicated problems, includes a book.
• Routing problems [The sweedish royal institute of Technology]: formal description ofthe famous routing problems also including literature and links.
• Routing in computer and telephone networks [Rensselaer Polytechnic Institute]: the basic concepts about routing are explained and an application is considered.

• Chinese Postman Problem:

• Chinese Postman Problem [The HongKong Polytechnic University]: a brief description including a lot of examples.
• Chinese Postman Problem from Mathworld [Mathworld]: a brief definition with examples.
• Chinese Postman and Euler Tour Problems in Bi-directed Graphs [Georgia institute of Technolog]: a complete guide for beginners.
• The Chinese Postman Problem [PolyU Hongkong]: a brief and complete text about the CPP with figures and explanations.

Shortest Path Problems

• Dijsktra's shortest path [Boost.org]: description and implementation in C++.
• Shortest Path Problem [Mathworld]: a short definition.
• Shortest Path Problem (Dijkstra's Algorithm) [University of Tokushima]: a very formal definition of Dijkstra's algorithm, including many demo applets and third party links.

Graph Coloring Problems

• Bipartite Graphs and the Four-Color Theorem [Lousiana state University Shreveport]: basic knowledge about the Four-Color Theory including further literature.
• The Four-Color Theorem a new proof for the Four-Color Theorem
• Four-Color Theorem Four-Color Theorem
• History of Four-Color Theorem History of Four-Color Theorem
• Diskrete Mathematik Themen [University of Bielefeld]: a website about discrete mathematics also contains many common topics like the four colors problem, including many third party links (in German and English)
• Edge Coloring from Mathworld [Mathworld]: a brief definitions with examples.
• Graph Coloring [Boost.org] : some basic concepts with an implementation of the smallest-last ordering algorithm.
• Graph Coloring Page [University of Alberta]: Graph bibliography, graph coloring programs, graph generator programs, and many other third party links.
• Map Coloring [University of Alabama]: a full guide for map coloring (from a graph algorithmic approach) includes a lot of examples.
• Network Resources for Coloring a Graph [Cornegie Mellon]: introduces graph coloring and contains a brief survey of the algorithms and applications of graph coloring.
• Vertex Coloring from Mathworld [Mathworld]: a brief definition with examples.

Matching Problems

• Bipartite Matching [Duke University]: a definition of a matching problem, MIN-CUT MAX-FLOW, FORD-FULKERSON method, etc. with some literature links
• Matching Algorithms [Algorithmicsolutions.info]: some basic concepts of matching, also its relation with Bipartite graphs.

Minimum Spanning Tree Problems

• Der Algorithmus von Kruskal [University of Freiburg]: animation of the Kruskal algorithm which determines the MST of a graph; (in German)
• Minimal spannender Baum [Netlexicon.de]: a detailed definition with an example (in German) contains a link to the English translation.
• Minimal spannender Baum [Wikipedia Encyclopedia]: another detailed definition with links to many MST algorithms (in German).
• Online construction of a minimal spanning tree (MST) [McGill University]: discussing the optimal algorithm for adding a point into an MST (the NearPoints algorithm) and some other topics.