Graphs

Theory - Algorithms - Complexity



This page collects information about graphs (here is a definition) and pointers to corresponding web resources. Supplementing, comments and suggestions are most welcome! Please inform me about expired links.

Many thanks to Laurence Pelletier, P. Ossona de Mendez, Victor Jimenez, and Pablo Moscato for contributions.

Contents:


Related Link Collections


Online Forums


Open Problems


Topics

Tutorials & Glossaries Glossary of some basic graph theoretic terms [Stephen C. Locke, Florida]; 
Graph Theory Tutorials and Glossary [Chris K. Caldwell, Tennessee] 
Graph Coloring Graph Coloring Problems - The Archive, updates of the book by Jensen and Toft (Denmark); The Graph Coloring Page by Joseph Culberson (Edmonton); The Four Color Theorem, by Robin Thomas; Network Resources for Coloring a Graph by M. Trick (Carnegie Mellon); Radio Channel Assignment by Mark Shepherd (Oxford); Max Clique Solver `clique here' by R. Battiti and M. Protasi (Trento); GRAPH COLORINGS WITH LOCAL CONSTRAINTS - A SURVEY by Tuza (Budapest) 
Graph Drawing Geometry in Action: Graph Drawing by David Eppstein; Graph Drawing by Tamassia (Brown); DFG-project Design, Analysis, Implementation, and Evaluation of Graph Drawing Algorithms; Graph Drawing by Arne Frick; Graph Visualization System daVinci; Graph Layout Toolkit by Tom Sawyer Software; Graphviz by AT&T Research, A Library of Algorithms for Graph Drawing
The Traveling Salesman
Problem
TSPLIB, by G. Reinelt (Heidelberg); TSPBIB, by P. Moscato (La Plata); David Neto's TSP reading list; Hamiltonian problems, by G. Gutin and P Moscato; Vašek Chvátal's TSP-page
Graph Partitioning Graph Partitioning: PARTY (Robert Preis, Ralf Diekmann); Chaco (Bruce A. Hendrickson, Robert Leland); METIS (George Karypis); Graph Partitioners (Miller, Teng, Blelloch); SCOTCH (François Pellegrini); Exact Methods (Stefan E. Karisch, Kobenhavn, and Franz Rendl, Graz); the Brunetta/Conforti/Rinaldi test instances; Kernighan-Lin, Simulated Annealing, and Path Optimization for MAX CUT and MIN QUOTIENT CUT by Jonathan Berry and Mark Goldberg
Approximation PCPs and Approximation, page by M. Bellare (San Diego); Approximation Algorithms Project, Hċstad/Kann/Lagergren (Stockholm); A compendium of NP optimization problems, by P. Crescenzi and V. Kann
Steiner Trees The Steiner tree page, by Joe Ganley (Virginia) 
Multicommodity Flows Test instances for Multicommodity Flow Problems at the University of Pisa. OR-Library, a set of operations research test problems, including GRAPH COLORING, PLANARIZATION, MATCHING, CLIQUE, MAX FLOW, and STEINER, by J.E. Beasley (Imperial College). A collection of test data for various mathematical programming problems (ZIB) 
Complexity ECCC - Electronic Colloquium on Computational Complexity (Trier); Parameterized Complexity Home Page, by M.T. Hallett and H.T. Wareham 
Misc Graph Class Inclusions (Andreas Brandstädt and Jens Westermann, Uni Rostock); 
Graph Families - tables on the complexity of optimization problems on various classes of graphs (Bing Xu) 
K Shortest Paths
Intersection Graphs
Index of Combinatorial Objects, page by Kris Coolsaet (Gent), and Cubic Cages, page by G. Royle (AU)
The (Degree,Diameter) Problem for Graphs, by Francesc Comellas (Barcelona)
Graceful graph labellings, by Michael Brundage
DFG-Research-Cluster "Discrete Algorithms"
GETGRATS - Graph Transformation Research Network
Local Search Algorithms and Metaheuristics

Search & Find...


Software


Books & Lecture Notes

Recent Text Books & Lecture Notes

Monographs

Anthologies

Other collections


Selected People

Daniel P. Sanders' list of A Few Graph Theorists' Home Pages
Network Programming People, a list compiled by Ernesto Martins
Alon, Noga (Tel Aviv)
Archdeacon, Dan (Vermont)
Arkin, Esther M. (Stony Brook)
Arnborg, Stefan (Stockholm)
Arora, Sanjeev (Princeton)
Bar-Yehuda, Reuven (Technion)
Blum, Avrim (Carnegie Mellon)
Bodlaender, Hans (Utrecht)
Bollobas, Bela (Memphis, TN)
Brandstädt, Andreas (Rostock)
Brandt, Stephan (Berlin)
Brunetta, Lorenzo (Milano)
Cameron, Peter (London)
Chartrand, Gary (Michigan)
Chung, Fan (Philadelphia)
Chvátal, Vašek (Piscataway, NJ)
Cook, William J. (Houston)
Corneil, Derek G. (Toronto)
Dean, Nathaniel (Bell Labs, NJ)
De Fraysseix, Hubert (C.N.R.S., Paris)
De Mendez, Patrice Ossona (C.N.R.S., Paris)
Diestel, Reinhard (Hamburg)
Djidjev, Hristo (Rice)
Eppstein, David (Irvine CA)
Erdös, Paul (see also The Erdös Number Project, and In Memoriam )
Fajtlowicz, S. (Houston TX)
Faudree, Ralph (Memphis)
Fellows, Michael (Victoria BC)
Fleischner, Herbert (Wien)
Frieze, Alan (Carnegie Mellon)
Garg, Naveen (Saarbrücken)
Godsil, Chris (Waterloo, CA)
Goemans, Michel X. (MIT)
Goldberg, Andrew V. (NEC Research Institute)
Goldberg, Mark K. (Troy)
Golumbic, Martin Charles (Bar-Ilan)
Grable, David A. (Berlin)
Grötschel, Martin (Berlin)
Grossman, Jerry (Oakland)
Gustedt, Jens (Berlin)
Halldorsson, Magnus M. (Reykjavik)
Harary, Frank (Las Cruces, NM)
Hassin, Refael (Tel Aviv)
Heath, Lenwood S. (Virginia Tech.)
Hoang, Chinh T. (Thunder Bay)
Hobbs, Arthur (Waterloo)
Hochbaum, Dorit (Berkeley)
Hougardy, Stefan (Berlin)
Hsu, Wen-Lian
Jensen, Tommy R. (Chemnitz)
Jerrum, Mark (Edinburgh)
Johnson, David (AT&T)
Jünger, Michael (Köln)
Kann, Vigo (Stockholm)
Karger, David R. (MIT)
Karisch, Stefan E. (Kobenhavn)
Karpinski, Marek (Bonn)
Kaufmann, Michael (Tübingen)
Khuller, Samir (Maryland)
Klein, Philip (Brown)
Kleinberg, Jon (Cornell)
Knuth, Don (Stanford)
Kocay, Bill (Winnipeg)
Kratochvil, Jan (Prague)
Kratsch, Dieter (Jena)
Kreuter, Bernd (Heidelberg)
Langston, Michael A. (Knoxville)
Van Leeuwen, J. (Utrecht)
Lengauer, Thomas (Sankt Augustin)
Lovasz, Laszlo (Yale)
Maffray, Frédéric (Grenoble)
Martins, Ernesto (Coimbra)
McConnell, Ross (Salem)
McDiarmid, Colin J. (Oxford)
McKay, Brendan (Australian National University)
Mehlhorn, Kurt (Saarbrücken)
Mohar, Bojan (Ljubljana)
Möhring, Rolf H. (Berlin)
Motwani, Rajeev (Stanford)
Naor, Joseph (Technion)
Nash-Williams, C.St.J.A. (Reading)
Nesetril, J. [Email]
Panconesi, Alessandro (Venezia)
Papadimitriou, Christos H. (Berkeley)
Penn, Michal (Haifa)
Plummer, Michael (Nashville)
Preissmann, Myriam (Grenoble)
Prisner, Erich (Hamburg)
Prömel, Hans-Jürgen (Berlin)
Proskurowski, Andrzej (Eugene)
Pulleyblank, William (IBM Watson)
Rabani, Yuval (Technion)
Raghavachari, Balaji (Dallas)
Ramachandran, Vijaya (Austin)
Ravi, R. (Carnegie Mellon)
Robinson, Robert W. (Georgia)
Royle, Gordon (Nedlands, AU)
Sanders, Daniel P. (Princeton)
Scheffler, Petra (Stralsund)
Scheinerman, Edward (Johns Hopkins)
Schelp, Richard (Memphis)
Shamir, Ron (Tel Aviv)
Shmoys, David B. (Cornell)
Sinclair, Alistair (Berkeley)
Spencer, Joel (Courant Institute)
Spinrad, Jerry (Vanderbilt)
Steger, Angelika (München)
Stewart, Lorna (Edmonton)
Székely, László (Columbia)
Tamassia, Roberto (Brown)
Tardos, Éva (Cornell)
Thomas, Robin (Georgia Tech)
Thomassen, Carsten (Denmark)
Toft, Bjarne (Odense)
Turau, Volker (Wiesbaden)
Tuza, Zsolt (Budapest) [E-Mail]
Vazirani, Vijay V. (Georgia Tech)
Wagner, Dorothea (Konstanz)
Weihe, Karsten (Konstanz)
Welsh, D.J.A (Oxford)
West, Douglas (Urbana)
Williamson, David P. (Watson)
Winter, Pawel (Kobenhavn)
Woodall, Douglas R. (Nottingham)
Wormald, Nick (Melbourne)
Yannakakis, Mihalis (Bell Labs)
Zachariasen, Martin (Kobenhavn)
Zelikovsky, Alexander (Los Angeles)
#hits hits since May-5-97. 
Thomas Emden-Weinert created: Oct-20th-96, last change: 2000/06/15