Stephen Travis Hedetniemi (* 7. Februar 1939)Geburtsdatum nach ihm gewidmeten Sammelband Gary Chartrand u. a. (Hrsg.), From Domination to Coloring, Springer 2019 ist ein US-amerikanischer Mathematiker und Informatiker.
Leben Hedetniemi studierte an der University of Michigan mit dem Bachelor-Abschluss in Mathematik 1960, dem Master-Abschluss 1962 und der Promotion 1966 in Communication Sciences bei Frank Harary (Homomorphisms of Graphs and Automata). Er war in der Gruppe für Computerlogik der University of Michigan und wurde 1967 Assistant Professor und 1969 Associate Professor in Informatik an der University of Iowa. Ab 1972 war er Associate Professor an der University of Virginia. Außerdem war er 1972 zwei Monate am Naval Weapons Laboratory in Dahlgren und 1975/76 Gastprofessor an der University of Victoria. 1977 bis 1982 war er Professor und Leiter der Abteilung für Informatik an der University of Oregon. Ab 1982 war er Professor an der Clemson University.
Er befasst sich mit Entwurf und Analyse von Algorithmen und Graphentheorie. Unter anderem befasste er sich mit dominierenden Mengen in Graphen (das heißt einer Untermenge D der Knoten, so dass jeder Knoten des Graphen zu einem Element von D benachbart ist) und gilt in diesem Gebiet als Pionier.
Von ihm stammt die in seiner Dissertation aufgestellte Vermutung von Hedetniemi, dass die chromatische Zahl des Tensorprodukts zweier Graphen G, H gleich dem Minimum der chromatischen Zahlen von G und H ist. Sie wurde 2019 durch ein Gegenbeispiel durch Yaroslav Shitov widerlegt.Shitov, Counterexamples to Hedetniemi's conjecture, Preprint, Arxiv 2019
Schriften (Auswahl) Homomorphisms of Graphs and Automata, University of Michigan Communications Sciences Program, Technical Report 03105-44-T, 1966 (Dissertation) mit E. J. Cockayne: Towards a theory of domination in graphs, Networks, Band 7, 1977, S. 247–261 mit E. J. Cockayne, R. M. Dawes: Total domination in graphs, Networks, Band 10, 1980, S. 211–219 mit P. J. Slater, E. J. Cockayne: Information dissemination in trees, SIAM Journal on Computing, Band 10, 1981, S. 692–701 mit S. M. Hedetniemi, A. L. Liestman: A survey of gossiping and broadcasting in communication networks, Networks, Band 18, 1988, S. 319–349 mit T. W. Haynes, P. Slater: Fundamentals of domination in graphs, CRC Press 1998 mit T. W. Haynes, P. J. Slater: Domination in Graphs: Advanced Topics, Monographs and Textbooks in Pure and Applied Mathematics 209, Marcel Dekker 1998 mit T. W. Haynes, S. M. Hedetniemi, M. A. Henning: Domination in graphs applied to electric power networks, SIAM Journal on Discrete Mathematics, Band 15, 2002, S. 519–529
Literatur Gary Chartrand, Teresa W. Haynes, Michael A. Henning, Ping Zhang (Hrsg.): From Domination to Coloring - Stephen Hedetniemi’s Graph Theory and Beyond, Springer 2019 (zum 80. Geburtstag von Hedetniemi)
Weblinks Homepage mit CV Stephen Travis Hedetniemi in der Datenbank zbMATH
Einzelnachweise
Kategorie:Mathematiker (20. Jahrhundert) Kategorie:Informatiker Kategorie:Hochschullehrer (Clemson University) Kategorie:Hochschullehrer (University of Oregon) Kategorie:Absolvent der University of Michigan Kategorie:US-Amerikaner Kategorie:Geboren 1939 Kategorie:Mann