Mensagem enviada à lista de discussão GRAPHNET por Jim Nastos em janeiro de 2004

Graph Theory Algorithms Top Ten

On Fri, 16 Jan 2004, Inge H. A. Pettersen wrote:

 > A more interesting question, in my view, would be to ask for the
 > top ten algorithms in graph theory.

A lot of graph theory is not restricted to algorithmic graph theory.  But if you were asking for a list of graph algorithms, are you interested algorithms most used/referenced?  Or algorithms accomplishing the most difficult tasks?  Simple but indispensible algorithms include trivial searches like DFS, BFS, or more specifically the LexBFS.

Is an exponential-time algorithm suitable for a top ten list?  Or an approximation algorithm?  These can include backtracking algorithms for clique-finding, the famous TSP solvers and Isomorphism checkers, all of which are very sophisticated.

Does optimization fall into graph algorithms?  Semi-definite programming has roots in perfect graph theory.

Obviously, anyone's list of 'favorite' algorithms would be very particular to their area of interest…  here is a list — not a 'top ten' list — but my ten favorite (in no particular order.)

• Rose, Tarjan, Lueker's linear time Lexicographic BFS
• McConnell & Spinrad's linear time Modular Decomposition (and transitive orientation)
• Grotschel, Lovasz, Shrijver's polytime optimization of perfect graphs
• Seymour & Chudnovsky's polytime recognition of Berge Graphs
• De Figueiredo, Klein, Kohayakawa, Reed's Polytime decomposition through Skew Partitions
• Hayward, Hougardy, Reed's Polytime recognition of P4-Structure
• Edmonds' graph matching algorithm
• Ibaraki & Nagamochi's edge-connectivity algorithm
• Applegate, Bixby, Chvatal, Cook's TSP solver CONCORDE
• McKay's Isomorphism/automorphism computing NAUTY

(Os grifos são meus)