Harold N. Gabow, genannt Hal Gabow, ist ein US-amerikanischer Informatiker.

Gabow studierte Mathematik an der Harvard University mit dem Bachelor-Abschluss summa cum laude 1968 und wurde 1973 bei Harold S. Stone an der Stanford University in Informatik promoviert ( Implementations of algorithms for maximum matching on nonbipartite graphs). Als Post-Doktorand war er an der University of Pennsylvania. Ab 1973 war er Assistant Professor, ab 1979 Associate Professor und ab 1986 Professor an der University of Colorado Boulder, an der er 2008 emeritiert wurde.

Gabow befasste sich mit Algorithmen und Datenstrukturen, speziell Graph-Algorithmen. Er trug zur Entwicklung von effizienten Algorithmen bei Flüssen, Kantenzusammenhang und Matching (Laudatio der Ernennung zum Fellow der ACM). Außerdem befasst er sich mit kombinatorischer Optimierung und Linearer Programmierung.

Nachdem Jack Edmonds 1965 einen polynomzeitlichen Algorithmus für das Matching-Problem fand (Matching sowohl mit maximaler Kardinalität (gleiche Gewichte) als auch für Kanten-gewichtete Graphen) suchte man nach schnelleren Algorithmen, auch mit anderen Methoden als Edwards. So führte Gabow Gewichts-Skalierung ein. Der schnellste Algorithmus für gewichtete Graphen ist der Algorithmus von Gabow und Robert Tarjan, der auf Gewichts-Skalierung aufbaut. 1983 verbesserte er mit Tarjan dessen Algorithmus zur Bestimmung des Lowest Common Ancestors für Knoten in Baumstrukturen auf Ausführung in linearer Zeit.

Er war 2004 Gründungsherausgeber der ACM Transactions on Algorithms (TALG), die ab 2005 erschien, nachdem bei der Vorläuferzeitschrift Journal of Algorithms (bei Elsevier erschienen) das gesamte Herausgeber-Team wegen der Preispolitik von Elsevier zurückgetreten war. Er blieb bis 2008 Chefherausgeber.

2002 wurde er Fellow der ACM und erhielt von dieser mehrere Distinguished Service Awards.

Gabow ist seit 1971 mit Patricia A. Gabow (* 1944), Medizinerin und emeritierte Professorin der University of Colorado School of Medicine, verheiratet. Sie haben eine Tochter und einen Sohn.

Einzelnachweise

  1. ↑ Harold N. Gabow im Mathematics Genealogy Project (englisch)
  2. ↑ Gabow, A scaling algorithm for weighted matching on general graphs, Proc. 26th Annual Symposium on Foundations of Computer Science, 1985, (FOCS’85), S. 90–100
  3. ↑ Gabow, Tarjan, Faster scaling algorithms for general graph matching problems, Journal of the ACM, Band 38, 1991, S. 815–853
  4. ↑ Gabow, Tarjan, A linear-time algorithm for a special case of disjoint set union, Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), 1983, S. 246–251
  5. ↑ Journal of Algorithms Resignation, Homepage von Gabow.
  6. ↑ International Who's who in Medicine. International Biographical Centre, Cambridge 1995, ISBN 0-948875-91-7, S. 152
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.