Stephen T. Hedetniemi

from Wikipedia, the free encyclopedia

Stephen Travis Hedetniemi (born February 7, 1939 ) is an American mathematician and computer scientist.

Life

Hedetniemi studied at the University of Michigan with a bachelor's degree in mathematics in 1960, a master's degree in 1962 and a doctorate in Communication Sciences in 1966 with Frank Harary (Homomorphisms of Graphs and Automata ). He was in the Computer Logic Group at the University of Michigan and became an Assistant Professor in 1967 and an Associate Professor in Computer Science in 1969 at the University of Iowa . From 1972 he was an associate professor at the University of Virginia . In 1972 he was two months at the Naval Weapons Laboratory in Dahlgren and 1975/76 visiting professor at the University of Victoria. From 1977 to 1982 he was Professor and Head of the Department of Computer Science at the University of Oregon . From 1982 he was a professor at Clemson University .

He deals with the design and analysis of algorithms and graph theory . Among other things, he dealt with dominating sets in graphs (i.e. a subset D of the nodes, so that each node of the graph is adjacent to an element of D) and is considered a pioneer in this area.

It was from him that Hedetniemi conjectured in his dissertation that the chromatic number of the tensor product of two graphs G, H is equal to the minimum of the chromatic numbers of G and H. It was refuted in 2019 by a counterexample by Yaroslav Shitov.

Fonts (selection)

  • Homomorphisms of Graphs and Automata, University of Michigan Communications Sciences Program, Technical Report 03105-44-T, 1966 (Dissertation)
  • with EJ Cockayne: Towards a theory of domination in graphs, Networks, Volume 7, 1977, pp. 247-261
  • with EJ Cockayne, RM Dawes: Total domination in graphs, Networks, Volume 10, 1980, pp. 211-219
  • with PJ Slater, EJ Cockayne: Information dissemination in trees, SIAM Journal on Computing, Volume 10, 1981, pp. 692-701
  • with SM Hedetniemi, AL Liestman: A survey of gossiping and broadcasting in communication networks, Networks, Volume 18, 1988, pp. 319-349
  • with TW Haynes, P. Slater: Fundamentals of domination in graphs, CRC Press 1998
  • with TW Haynes, PJ Slater: Domination in Graphs: Advanced Topics, Monographs and Textbooks in Pure and Applied Mathematics 209, Marcel Dekker 1998
  • with TW Haynes, SM Hedetniemi, MA Henning: Domination in graphs applied to electric power networks, SIAM Journal on Discrete Mathematics, Volume 15, 2002, pp. 519-529

literature

  • Gary Chartrand, Teresa W. Haynes, Michael A. Henning, Ping Zhang (Eds.): From Domination to Coloring - Stephen Hedetniemi's Graph Theory and Beyond, Springer 2019 (on the 80th birthday of Hedetniemi)

Web links

Individual evidence

  1. ↑ Date of birth according to the anthology Gary Chartrand u. a. (Ed.), From Domination to Coloring, Springer 2019
  2. ↑ Stephen T. Hedetniemi in the Mathematics Genealogy Project (English)Template: MathGenealogyProject / Maintenance / id used
  3. ↑ Shitov, Counterexamples to Hedetniemi's conjecture , Preprint, Arxiv 2019
personal data
SURNAME Hedetniemi, Stephen T.
ALTERNATIVE NAMES Hedetniemi, Stephen Travis
BRIEF DESCRIPTION American computer scientist and mathematician
DATE OF BIRTH February 7, 1939