RESUMÉ - Stephen T. Hedetniemi

PERSONAL DATA

EDUCATION

PROFESSIONAL EXPERIENCE

MEMBERSHIPS

PUBLICATIONS

Books and Chapters

Refereed Journal Publications

Refereed Conference Publications

Technical Reports

PERSONAL DATA

Professor, Division of Computer Science

School of Computing

Clemson University

Clemson, South Carolina 29634-0974

Phone: (864) 656-5858

Email: hedet@cs.clemson.edu

FAX: (864) 656-0145

Born: February 7, 1939, Washington, D.C.

Married: Sandra M. Hedetniemi (Professor of Computer Science, Clemson University)

EDUCATION

Diploma, George Mason Jr. Sr. High School, Falls Church, Virginia, 1956

B.S., University of Michigan, 1960, Mathematics

M.S., University of Michigan, 1962, Communication Sciences

Ph.D., University of Michigan, 1966, Communication Sciences

PROFESSIONAL EXPERIENCE

Clemson University, School of Computing

1997-present, Professor

1994-1997, Professor and Head/Chair

1992-1994, Professor and Acting Head

1982-1992, Professor

University of Oregon, Dept. of Computer and Inf. Science

1977-1982, Professor and Head

University of Virginia, Dept. of Applied Mathematics and Computer Science

1972-1976, Associate Professor

1971-1972, Visiting Associate Professor

University of Victoria, Department of Mathematics

1975-1976, Visiting Associate Professor

Naval Weapons Laboratory, Dahlgren, Virginia

July 1972 - August 1972, Mathematician

University of Iowa, Department of Computer Science

1969-1971, Associate Professor

1967-1969, Assistant Professor

University of Michigan, Logic of Computers Group

1966-1967, Research Associate

1963-1967, Research Assistant

National Bureau of Standards, Washington, D.C.

Summers of 1960, 1961, 1962, Mathematician

Department of the Army, Medical Information and Intelligence Agency, Arlington, VA

Summers of 1958, 1959, Clerk typist

Department of the Army, Overseas Affairs Division, Washington, D.C.

Summers of 1956, 1957, Clerk typist

 

MEMBERSHIPS

Fellow, Institute of Combinatorics and its Applications

PUBLICATIONS

Books and Chapters

S.E. Goodman and S.T. Hedetniemi, Introduction to the Design and Analysis of Algorithms, McGraw-Hill, New York (1977), 371 pp.

S.E. Goodman and S.T. Hedetniemi, A descriptive introduction to graph theory and some of its applications, Chapter 1 in Computers in Language Research, W.A. Sedelow and S.Y. Sedelow, Eds., Mouton, The Hague (1979), pp. 19-95.

S.T. Hedetniemi and R.C. Laskar, Eds., Topics in Domination, Annals of Discrete Mathematics, Vol. 48, North Holland, Amsterdam (1990), 280 pp.

S. Arnborg, S. Hedetniemi and A. Proskurowski, Eds., Special Issue: Efficient Algorithms and Partial K-trees, Discrete Appl. Math. 564(2-3) (1994), 290 pp.

T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York (1998), 446 pp.

T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Eds., Domination in Graphs: Advanced Topics Marcel Dekker, New York (1998), 497 pp.

S.M. Hedetniemi, S.T. Hedetniemi and R. Reynolds, Combinatorial problems on chessboards: II, Chapter 6 in Domination in Graphs: Advanced Topics, T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Eds., Marcel Dekker, New York (1998), pp. 133-162.

S.T. Hedetniemi, A. A. McRae and D.A. Parks, Complexity results, Chapter 9 in Domination in Graphs: Advanced Topics, T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Eds., Marcel Dekker, New York (1998), pp. 233-269.

Refereed Journal Publications

F. Harary, S. Hedetniemi and G. Prins, An interpolation theorem for graphical homomorphisms, Portugal. Math. 26:453-462, 1967.

G. Chartrand, D. Geller and S. Hedetniemi, A generalization of the chromatic number, Proc. Camb. Philos. Soc. 64:265-271, 1968.

S. Hedetniemi, On partitioning planar graphs, Canad. Math. Bull. 11:203-211, 1968.

S. Hedetniemi, On minimum walks in graphs, Naval Res. Logistics Quarterly 15:453-458, 1968.

F. Harary, S. Hedetniemi and R. Robinson, Uniquely colorable graphs, J. Combin. Theory 6:264-270, 1969.

F. Harary and S. Hedetniemi, The achromatic number of a graph, J. Combin. Theory 8:154-161, 1970.

G. Chartrand, D. Geller and S. Hedetniemi, Graphs with forbidden subgraphs, J. Combin. Theory 10:12-41, 1971.

A.C. Fleck, S.T. Hedetniemi and R.H. Oehmke, S-semigroups of automata, J. Assoc. Comput. Mach. 19:3-10, 1972.

S. Hedetniemi, Hereditary properties of graphs, J. Combin. Theory 14:94-99, 1973.

S.E. Goodman and S.T. Hedetniemi, Eulerian walks in graphs, SIAM J. Comput. 2:16-27, 1973.

S.E. Goodman and S.T. Hedetniemi, Sufficient conditions for a graph to be Hamiltonian, J. Combin. Theory 16:175-180, 1974.

S.E. Goodman and S.T. Hedetniemi, On Hamiltonian walks in graphs, SIAM J. Comput. 3:214-221, 1974.

S.E. Goodman, S.T. Hedetniemi and P.J. Slater, Advances on the Hamiltonian completion problem, J. Assoc. Comput. Mach. 22:352-360, 1975.

E.J. Cockayne, S.E. Goodman and S.T. Hedetniemi, A linear algorithm for the domination number of a tree, Inform. Process. Lett. 4:41-44, 1975.

E.J. Cockayne and S.T. Hedetniemi, Optimal domination in graphs, IEEE Trans. Circuits Systems CAS 22:855-857, 1975.

E.J. Cockayne and S.T. Hedetniemi, Disjoint independent dominating sets in graphs, Discrete Math. 15:213-222, 1976.

E.J. Cockayne and S.T. Hedetniemi, Which trees do not have disjoint maximal matchings?, Utilitas Math. 9:329-337, 1976.

P.J. Slater, S.E. Goodman and S.T. Hedetniemi, On the optional Hamiltonian completion problem, Networks 6:35-51, 1976.

S. Goodman, S. Hedetniemi and R.E. Tarjan, B-matchings in trees, SIAM J. Comput. 5:104-107, 1976.

E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7:247-261, 1977.

S.T. Hedetniemi and D.M. Spresser, A property of trees in terms of unique connected subgraphs, J. Graph Theory 1:335-338, 1977.

E.J. Cockayne and S.T. Hedetniemi, Disjoint cliques in regular graphs of degree seven and eight, J. Combin. Theory 34:233-237, 1978.

E.J. Cockayne, B.L. Hartnell and S.T. Hedetniemi, A linear algorithm for disjoint matchings in trees, Discrete Math. 21:129-136, 1978.

E.J. Cockayne, S.T. Hedetniemi and D.J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull. 21:461-468, 1978.

E.J. Cockayne, S.T. Hedetniemi and P.J. Slater, Matchings and transversals in hypergraphs, domination and independence in trees, J. Combin. Theory 26:78-80, 1979.

S.L. Mitchell, E.J. Cockayne and S.T. Hedetniemi, Linear algorithms on recursive representations of trees, J. Comput. System Sci. 18:76-85, 1979.

A. Farley, S. Hedetniemi, S. Mitchell and A. Proskurowski, Minimum broadcast graphs, Discrete Math. 25:189-193, 1979.

S.L. Mitchell and S.T. Hedetniemi, Linear algorithms for edge colorings of trees and unicyclic graphs, Inform. Process. Lett. 9:110-112, 1979.

S.L. Mitchell and S.T. Hedetniemi, A census of minimum broadcast graphs, J. Combin. Inform. System Sci. 5:119-129, 1980.

E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10:211-219, 1980.

A. Farley, S. Hedetniemi and S. Mitchell, Rectilinear Steiner trees in rectangle trees, SIAM J. Algebraic and Discrete Meth. 1:70-81, 1980.

P.J. Slater, E.J. Cockayne and S.T. Hedetniemi, Information dissemination in trees, SIAM J. Comput. 10:692-701, 1981.

S.M. Hedetniemi, E.J. Cockayne and S.T. Hedetniemi, Linear algorithms for the Jordan centre and path centre of a tree, J. Transportation Sci. 15:98-114, 1981.

S.M. Hedetniemi, S.T. Hedetniemi and P.J. Slater, A note on packing trees into K_n, Ars Combin. 11:149-153, 1981.

A. Farley, S. Hedetniemi and A. Proskurowski, Partitioning trees: matching, domination and maximum diameter, Internat. J. Comput. Info. Sci. 10:55-61, 1981.

S.M. Hedetniemi, S.T. Hedetniemi and P.J. Slater, Centers and medians of C_n-trees, Utilitas Math. 21:225-234, 1982.

S.M. Hedetniemi and S.T. Hedetniemi, Vertex and edge deletion algorithms for trees, J. Combin. Inform. System Sci. 7:125-133, 1982.

R. Laskar, J. Pfaff, S.M. Hedetniemi and S.T. Hedetniemi, On the algorithmic complexity of total domination, SIAM J. Alg. Disc. Meth. 5:420-425, 1984.

R. Allan, R. Laskar and S. Hedetniemi, A note on total domination, Discrete Math. 49:7-13, 1984.

S.T. Hedetniemi, R. Laskar and J. Pfaff, A linear algorithm for finding a minimum dominating set in a cactus, Discrete Appl. Math. 13:287-292, 1986.

E.J. Cockayne and S.T. Hedetniemi, On the diagonal queens domination problem, J. Combin. Theory 42:137-139, 1986.

K. Peters, R. Laskar and S. Hedetniemi, Maximal/minimal connectivity in graphs, Ars Combin. 21:59-70, 1986.

P. Erdös, W.R. Hare, S.T. Hedetniemi and R. Laskar, On the equality of the Grundy and ochromatic numbers of a graph, J. Graph Theory 11(2):157-159, 1987.

S.M. Hedetniemi, S.T. Hedetniemi and A.L. Liestman, A survey of gossiping and broadcasting in communication networks, Networks 18(4):319-359, 1988.

E.J. Cockayne, S.T. Hedetniemi and R. Laskar, Gallai theorems for graphs, hypergraphs and set systems, Discrete Math. 72:35-47, 1988.

M.O. Alberston, R.E. Jamison, S.T. Hedetniemi and S.C. Locke, The subchromatic number of a graph, Discrete Math. 74:33-49, 1989.

G.A. Cheston, A. Farley, S.T. Hedetniemi and A. Proskurowski, Centering a spanning tree of a biconnected graph, Inform. Process. Lett. 32:247-250, 1989.

S.T. Hedetniemi, D.P. Jacobs and R. Laskar, Inequalities involving the rank of a graph, J. Combin. Math. Combin. Comput. 6:173-176, 1989.

G.A. Cheston, G. Fricke, S.T. Hedetniemi and D. P. Jacobs, On the computational complexity of upper fractional domination, Discrete Appl. Math. 27:195-207, 1990.

S.T. Hedetniemi and R.C. Laskar, Introduction, Discrete Math. 86:3-9, 1990.

S.T. Hedetniemi and R.C. Laskar, Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Math. 86:257-277, 1990.

P.J. Bernhard, S.T. Hedetniemi and D.P. Jacobs, Efficient sets in graphs, Discrete Appl. Math. 44:99-108, 1993.

S.M. Hedetniemi, S.T. Hedetniemi and D.P. Jacobs, Total irredundance in graphs: theory and algorithms, Ars Combin. 35A:271-284, 1993.

E.J. Cockayne, B.L. Hartnell, S.T. Hedetniemi and R. Laskar, Perfect domination in graphs, J. Combin. Inform. System Sci. 18:136-148, 1993.

M. Fellows, G. Fricke, S. Hedetniemi and D. Jacobs, The private neighbor cube, SIAM J. Discrete Math. 7:41-47, 1994.

R. Labahn, S.T. Hedetniemi and R. Laskar, Periodic gossiping on trees, Discrete Appl. Math. 53:235-245, 1994.

N. Chandrasekharan, S. Hedetniemi and T. Wimer, Enumeration techniques for certain k-terminal families of graphs, J. Combin. Inform. System Sci. 19:121-138, 1994.

G.H. Fricke, S.T. Hedetniemi and M.A. Henning, Asymptotic results on distance independent domination in graphs, J. Combin. Inform. System Sci. 20:160-174, 1995.

J. Dunbar, F. Harris, S.M. Hedetniemi, S.T. Hedetniemi, R. Laskar and A. McRae, Nearly perfect sets in graphs, Discrete Math. 138:229-246, 1995.

G.H. Fricke, S.T. Hedetniemi and M.A. Henning, Distance independent domination in graphs, Ars Combin. 41:33-44, 1995.

E.J. Cockayne, G. Fricke, S.T. Hedetniemi and C.M. Mynhardt, Properties of minimal dominating functions of graphs, Ars Combin. 41:107-115, 1995.

J. Dunbar, S.T. Hedetniemi, M.A. Henning, Minus domination in regular graphs, Discrete Math. 149:311-312, 1996.

J. Dunbar, W. Goddard, S. Hedetniemi, A. McRae and M.A. Henning, The algorithmic complexity of minus domination in graphs, Discrete Appl. Math. 68:73-84, 1996.

G.H. Fricke, S.T. Hedetniemi and D.P. Jacobs, Maximal irredundant functions, Discrete Appl. Math. 68:267-277, 1996.

G.H. Fricke, S.T. Hedetniemi, D.P. Jacobs and V. Trevisan, Reducing the adjacency matrix of a tree, Electronic J. Linear Algebra 1:34-43, 1996.

J.E. Dunbar, J.W. Grossman, J.H. Hattingh, S.T. Hedetniemi and A.A. McRae, On weakly connected domination in graphs, Discrete Math. 167/168:261-269, 1997.

J.H. Yan, G.J. Chang, S.M. Hedetniemi and S.T. Hedetniemi, k-Path partitions in trees, Discrete Appl. Math. 78:227-233, 1997.

E.J. Cockayne, J.H. Hattingh, S.M. Hedetniemi, S.T. Hedetniemi and A.A. McRae, Using maximality and minimality conditions to construct inequality chains, Discrete Math. 176:43-61, 1997.

S.M. Hedetniemi, S.T. Hedetniemi and M.A. Henning, The algorithmic complexity of perfect neighborhoods in graphs, J. Combin. Math. Combin. Comput. 25:183-192, 1997.

E.J. Cockayne, P.J.P. Grobler, S.T. Hedetniemi and A.A. McRae, What makes an irredundant set maximal?, J. Combin. Math. Combin. Comput. 25:213-224, 1997.

G.H. Fricke, S.T. Hedetniemi and D.P. Jacobs, Independence and irredundance in k-regular graphs, Ars Combin. 49:271-279, 1998.

E.J. Cockayne, S.M. Hedetniemi, S.T. Hedetniemi and C.M. Mynhardt, Irredundant and perfect neighbourhood sets in trees, Discrete Math. 188:253-260, 1998.

G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar and L.R. Markus, Restrained domination in graphs, Discrete Math. 203(1-3):61-69, 1999.

J. Dunbar, S. Hedetniemi, M.A. Henning and A. McRae, Minus domination in graphs, Discrete Math.199:35-47, 1999.

S.M. Hedetniemi, S.T. Hedetniemi and D.P. Jacobs, Rank independent domination for trees, Bull. Inst. Combin. Appl. 27:62-68, 1999.

G.H. Fricke, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, and M.A. Henning, On perfect neighborhood sets in graphs, Discrete Math.199:221-225, 1999.

J.E. Dunbar, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely, R.C. Laskar and D.F. Rall, Fall colorings of graphs, J. Combin. Math. Combin. Comput. 33:257-273, 2000.

S.M. Hedetniemi, S.T. Hedetniemi and D.F. Rall, Acyclic domination in graphs, Discrete Math. 222:151-165, 2000.

X. Baogen, E.J. Cockayne, T.W. Haynes, S.T. Hedetniemi and Z. Shangchao, Extremal graphs for inequalities involving domination parameters, Discrete Math. 216:1-10, 2000.

A.M. Abdelbar, S.T. Hedetniemi and S.M. Hedetniemi, The complexity of approximating MAPs for belief networks, J. Artificial Intelligence 124:283-288, 2000.

T.W. Haynes, S.M. Hedetniemi and S.T. Hedetniemi, Domination and independence subdivision numbers of graphs, Discussiones Mathematicae: Graph Theory 20(2):271-280, 2000.

S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, Maximal matching stabilizes in time O(m), Inform. Process. Lett. 80:221-223, 2001.

T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely and L.C. van der Merwe, Domination subdivision numbers, Discussiones Mathematicae: Graph Theory 21(2):239-253, 2001.

T.W. Haynes, S.T. Hedetniemi, M.A. Henning and D.J. Knisley, Stable and unstable graphs with total irredundance number zero, Ars Combin. 61:33-46, 2001.

G.H. Fricke, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi and R.C. Laskar, Excellent trees, Bull. ICA 34:27-38, 2002.

O. Favaron, S.M. Hedetniemi, S.T. Hedetniemi and D.F. Rall, On k-dependent domination, Discrete Math. 249:83-94, 2002.

T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, and M.A. Henning, Power domination in graphs applied to electrical power networks, SIAM J. Discrete Math. 15(4):519-529, 2002.

O. Favaron, T. Haynes, S.T. Hedetniemi, M.A. Henning and D. Knisely, Total irredundance in graphs, Discrete Math. 256:115-127, 2002.

T.W. Haynes, S.T. Hedetniemi, M.A. Henning and P.J. Slater, H-forming sets in graphs, Discrete Math. 262:159-169, 2003.

T.W. Haynes, S.T. Hedetniemi and L.C. van der Merwe, Total domination subdivision numbers, J. Combin. Math. Combin. Comput. 44:115-128, 2003.

G.H. Fricke, L.M. Lawson, T.W. Haynes, S.M. Hedetniemi and S.T. Hedetniemi, A note on defensive alliances in graphs, Bull. ICA 38:37-41, 2003.

M.A. Henning and S.T. Hedetniemi, Defending the Roman Empire - A new strategy, Discrete Math. 266:239-251, 2003.

S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, Linear time self-stabilizing colorings, Inform. Process. Lett. 87:251-255, 2003.

P. Erdos, S.T. Hedetniemi, R.C. Laskar and G. Prins, On the equality of the partial Grundy and upper ochromatic numbers of graphs, Discrete Math. 272:53-64, 2003.

S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, Self-stabilizing algorithms for minimal dominating sets and maximal independent sets, Comput. Math. Appl. 46:803-811, 2003.

T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Global defensive alliances in graphs, Electronic J. Combin. 10(1):R47, 2003.

K.B. Reid, A.A. McRae, S.M. Hedetniemi and S.T. Hedetniemi, Domination and irredundance in tournaments, Australasian J. Combin. 29:157-172, 2004.

E.J. Cockayne, P.A. Dreyer, Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278:11-22, 2004.

S.M. Hedetniemi, S.T. Hedetniemi and P. Kristiansen, Alliances in graphs, J. Combin. Math. Combin. Comput. 48:157-177, 2004.

M. Gairing, W. Goddard, S.T. Hedetniemi and D.P. Jacobs, Self-stabilizing maximal k-dependent sets in linear time, Parallel Process. Lett. 14(1):75-82, 2004.

Z. Shi, W. Goddard, and S.T. Hedetniemi, An anonymous self-stabilizing algorithm for 1-maximal independent set in trees, Inform. Process. Lett. 91:77-83, 2004.S.M. Hedetniemi, S.T. Hedetniemi, A.A. McRae, D. Parks and J.A. Telle, Iterated colorings of graphs, Discrete Math. 278:81-108, 2004.

M. Gairing, R.E. Geist, S.T. Hedetniemi and P. Kristiansen, A self-stabilizing algorithm for maximal 2-packing, Nordic J. Comput. 11(1):1-11, 2004.

O. Favaron, T.W. Haynes and S.T. Hedetniemi, Domination subdivision numbers in graphs, Utilitas Math. 66:195-209, 2004.

O. Favaron, G. Fricke, W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, P. Kristiansen, R.C. Laskar and R.D. Skaggs, Offensive alliances in graphs, Discussiones Math. Graph Theory 24:263-275, 2004.

T.W. Haynes, S.T. Hedetniemi and M.A. Henning, A characterization of trees with equal domination and global strong alliance numbers, Utilitas Math. 66:105-119, 2004.

W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52:169-180, 2005.

W. Goddard, S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, Self-stabilizing algorithms for orderings and colorings, Int. J. Foundations of Comput. Sci. 16(1):19-36, 2005.

W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi and R. Laskar, Generalized subgraph-restricted matchings in graphs, Discrete Math. 293:129-138, 2005.J.E. Dunbar, T.W. Haynes and S.T. Hedetniemi, Nordhaus-Gaddum bounds for domination sums in graphs with specified minimum degree, Utilitas Math. 67:97-105, 2005.

W. Goddard, S.T. Hedetniemi, D.P. Jacobs, and P.K. Srimani, Self-stabilizing global optimization algorithms for large network graphs, Internat. J. Dist. Sensor Networks 1:329-344, 2005.

Z. Shi, W. Goddard, S.T. Hedetniemi, K. Kennedy, R. Laskar, and A. McRae, An algorithm for partial Grundy number on trees, Discrete Math. 304:108-116, 2005.

J.R.S. Blair, W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi and S.B. Horton, Domination equivalence in graphs, AKCE Internat. J. Graphs Combin. 2(2):123-136, 2005.

J.E. Dunbar, D.J. Erwin, T.W. Haynes, S.M. Hedetniemi and S.T. Hedetniemi, Broadcasts in graphs, Discrete Appl. Math. 154(1):59-75, 2006.

T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, J.R. Lewis and P.J. Slater, Differentials in graphs, Util. Math. 69:43-54, 2006.

S.T. Hedetniemi, Unsolved algorithmic problems on trees, AKCE Internat. J. Graphs Combin. 3:1-37, 2006.

G.H. Fricke, S.T. Hedetniemi and D.P. Jacobs, On the equivalence of the upper irredundance and fractional upper irredundance numbers in graphs, Bull. ICA 48:99-106, 2006.

R.C. Brigham, R.D. Dutton and S.T. Hedetniemi, Security in graphs, Discrete Appl. Math. 155:1708-1714, 2007.

J.R.S. Blair, W. Goddard, S.T. Hedetniemi, S. Horton, P. Jones and G. Kubicki, On domination and reinforcement numbers in trees, Discrete Math. 308:1165-1175, 2008.

W. Goddard, S.T. Hedetniemi, D.P. Jacobs, P.K. Srimani and Z. Xu, Self-stabilizing graph protocols, Parallel Process. Lett. 18(1):189-199, 2008.

W. Goddard, S.T. Hedetniemi, D.P. Jacobs and V. Trevisan, Distance-k knowledge in self-stabilizing algorithms, Theoretical Comput. Sci. 399:118-127, 2008.

W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, J.M. Harris and D.F. Rall, Broadcast chromatic numbers of graphs, Ars Combin. 86:33-49, 2008.

T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, A.A. McRae and P.J. Slater, Irredundant colorings of graphs, Bull. ICA 54:93-121, 2008.

S.M. Hedetniemi, S.T. Hedetniemi, D.F. Rall and J. Knisely, Secondary domination in graphs, AKCE Internat. J. Graphs Combin. 5(2):103-115, 2008.

A.C. Jamieson, W. Goddard and S.T. Hedetniemi, On the Wimer method for designing edge-based algorithms, AKCE Internat. J. Graphs Combin. 5(2):117-125, 2008.

Refereed Conference Publications

B. Levin and S. Hedetniemi, Determining fastest routes using fixed schedules, AFIPS Conf. Proc. 23:1-8, 1963.

D. Geller and S. Hedetniemi, A proof technique in graph theory, in Proof Techniques in Graph Theory, F. Harary, Ed., Academic Press, New York, pp. 49-59, 1969.

S. Hedetniemi, On classes of graphs defined by special cutsets of lines, in The Many Facets of Graph Theory, G. Chartrand and S.F. Kapoor, Eds., Springer-Verlag, Berlin, pp. 453-458, 1969.

S. Hedetniemi, A note on a category of graphs, in The Many Facets of Graph Theory, G. Chartrand and S.F. Kapoor, Eds., Springer-Verlag, Berlin, pp. 89-90, 1969.

S. Hedetniemi, Disconnected colorings of graphs, in Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer and J. Schonheim, Eds., Gordon and Breach, New York, pp. 163-167, 1970.

S. Hedetniemi, Graphs of (0,1)-matrices, in Recent Trends in Graph Theory, M. Capobianco, J.B. Frechen and M. Krolik, Eds., Springer-Verlag, Berlin, pp. 157-172, 1971.

S. Hedetniemi, Characterizations and constructions of minimally 2- connected graphs and minimally strong digraphs, Proc. Second Louisiana Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 257-282, 1971.

S.T. Hedetniemi and P.J. Slater, Line graphs of triangleless graphs and iterated clique graphs, in Graph Theory and Applications, Y. Alavi, D.R. Lick, and A.T. White, Eds., Springer-Verlag, Berlin, pp. 139-149, 1972.

E.J. Cockayne and S.T. Hedetniemi, Interpolation systems, Proc. Third Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 117-130, 1972.

S.E. Goodman, S.T. Hedetniemi and P.J. Slater, Some results on the optional and non-optional Hamiltonian completion problem, Proc. Fifth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematics, Winnipeg, pp. 423-448, 1974.

E.J. Cockayne and S.T. Hedetniemi, Independence graphs, Proc. Fifth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematics, Winnipeg, pp. 471-491, 1974.

S.E. Goodman and S.T. Hedetniemi, On the Hamiltonian completion problem, in Graphs and Combinatorics, 1973 R.A. Bari and F. Harary, Eds., Springer-Verlag, Berlin, pp. 262-272, 1974.

S. Mitchell, S. Hedetniemi and S. Goodman, Some linear algorithms on trees, Proc. Sixth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 467-483, 1975.

E.J. Cockayne and S.T. Hedetniemi, Graphes de groupes avec cliques maximales disjointes, Colloques Internationaux C.N.R.S. No. 260, Problems Combinatoires et Theorie des Graphes, Orsay, pp. 81-82, 1976.

E.J. Cockayne and S.T. Hedetniemi, A linear algorithm for the maximum weight of an independent set in a tree, Proc. Seventh Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 217-228, 1976.

T. Beyer, A. Proskurowski, S. Hedetniemi and S. Mitchell, Independent domination in trees, Proc. Eighth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 321-328, 1977.

S. Mitchell and S. Hedetniemi, Edge domination in trees, Proc. Eighth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 489-511, 1977.

A. Farley and S. Hedetniemi, Broadcasting in grid graphs, Proc. Ninth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 275-288, 1978.

P. Chinn, S. Hedetniemi and S. Mitchell, Multiple message broadcasting in complete graphs. Proc. Tenth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 251-260, 1979.

S.M. Hedetniemi, S.T. Hedetniemi and P.J. Slater, Which grids are Hamiltonian?, Proc. Eleventh Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 511-524, 1980.

T. Beyer, S.M. Hedetniemi, S.T. Hedetniemi and A. Proskurowski, Graph traversal with minimum stack depth, Proc. Twelfth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 121-130, 1981.

T. Beyer, S.M. Hedetniemi and S.T. Hedetniemi, A linear algorithm for the Grundy number of a tree, Proc. Thirteenth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 351-363, 1982.

S.M. Hedetniemi and S.T. Hedetniemi, Reducing space and time requirements for processing trees, Congr. Numer. 40:3-22, 1983.

S.T. Hedetniemi, A max-min relationship between matchings and domination in graphs, Congr. Numer. 40:23-34, 1983.

S. Hedetniemi and R. Laskar, Connected domination in graphs, in Graph Theory and Combinatorics, , B. Bollobas, Ed., Academic Press, London, pp. 209-218, 1984.

S.M. Hedetniemi, S.T. Hedetniemi and R. Laskar, Domination in trees: models and algorithms, in Graph Theory with Applications to Algorithms and Computer Science, Y. Alavi, G. Chartrand, L. Lesniak, D.R. Lick and C.E. Wall, Eds., (Kalamazoo, Mich., 1984), Wiley-Intersci. Publ., Wiley, New York, pp. 423-442, 1984.

G. Cheston and S. Hedetniemi, Polling in tree networks, Proc. Second West Coast Conf. on Combinatorics, Graph Theory and Computing, (Eugene, OR, 1983), Congr. Numer. 41:7-20, 1984.

J. Pfaff, R. Laskar and S. Hedetniemi, Linear algorithms for independent domination and total domination in series-parallel graphs, Congr. Numer. 45:71-82, 1984.

E.J. Cockayne, E.O. Hare, S.T. Hedetniemi and T.V. Wimer, Bounds for the domination number of grid graphs, Congr. Numer. 47:217-228, 1985.

E.O. Hare and S.T. Hedetniemi, The certificate: a canonical data structure for trees, Congr. Numer. 48:153-170, 1985.

W.R. Hare, S.T. Hedetniemi, R. Laskar and J. Pfaff, Complete coloring parameters of graphs, Congr. Numer. 48:171-178, 1985.

S. Hedetniemi, R. Laskar and J. Pfaff, Irredundance in graphs: a survey, Congr. Numer. 48:183-194, 1985.

T.V. Wimer, S.T. Hedetniemi and R. Laskar, A methodology for constructing linear graph algorithms, Proc. Sundance Conf., (Sundance, UT, 1985), Congr. Numer. 50:43-60, 1985.

W.R. Hare, E.O. Hare and S.T. Hedetniemi, Bandwidth of grid graphs, Proc. Sundance Conf., (Sundance, UT, 1985), Congr. Numer. 50:67-76, 1985.

E.O. Hare, W.R. Hare and S.T. Hedetniemi, Another upper bound for the bandwidth of trees, Proc. Sundance Conf., (Sundance, UT, 1985), Congr. Numer. 50:77-84, 1985.

G.S. Domke, R. Laskar, S.T. Hedetniemi and K. Peters, The partite-chromatic number of a graph, Congr. Numer. 53:235-246, 1986.

K. Peters, R. Laskar and S.T. Hedetniemi, On the strength of a graph, Congr. Numer. 53:247-262, 1986.

S. Hedetniemi and R. Laskar, A bipartite theory of graphs: I, Congr. Numer. 55:5-14, 1986.

E.O. Hare, S.T. Hedetniemi and W.R. Hare, Algorithms for computing the domination number of KxN complete grid graphs, Congr. Numer. 55:81-92, 1986.

E.O. Hare and S.T. Hedetniemi, A linear algorithm for computing the knight's domination number of a KxN chessboard, Congr. Numer. 59:115-130, 1987.

E. Hare, S. Hedetniemi, R. Laskar, K. Peters and T. Wimer, Linear time computability of combinatorial problems on generalized series-parallel graphs, Proc. Japan-U.S. Joint Seminar on Discrete Algorithms and Complexity Theory, (Kyoto, Japan, 1986), Perspectives in Computing 15:437-457,, Academic Press, 1987.

G. Domke, S. Hedetniemi, R. Laskar and R. Allan, Generalized packing and coverings of graphs, Congr. Numer. 62:259-270, 1988.

N. Chandrasekharan and S. Hedetniemi, Fast parallel algorithms for tree decomposing and parsing partial k-trees, Proc. Twenty-sixth Annual Allerton Conf. on Communication Control and Computing, (Urbana, IL, 1988).

T.V. Wimer and S.T. Hedetniemi, K-terminal recursive families of graphs, Proc. 250th Anniversary Conf. on Graph Theory, (Ft. Wayne, IN, 1986), Congr. Numer. 63:161-176, 1988.

G.S. Domke, R. Laskar and S.T. Hedetniemi, The edge subchromatic number of a graph, Proc. 250th Anniversary Conf. on Graph Theory, (Ft. Wayne, IN, 1986), Congr. Numer. 64:95-104, 1988.

S. Hedetniemi and R. Laskar, A bipartite theory of graphs: II, Proc. 250th Anniversary Conf. on Graph Theory, (Ft. Wayne, IN, 1986), Congr. Numer. 64:137-146, 1988.

S. Hedetniemi and R. Laskar, Recent results and open problems in domination theory, in Applications of Discrete Mathematics , R.O. Ringeisen and F.S. Roberts, Eds., SIAM, Philadelphia, pp. 205-218, 1988.

G.A. Cheston, E.O. Hare, S.T. Hedetniemi and R.C. Laskar, Simplicial graphs, Congr. Numer. 67:105-113, 1988.

G.S. Domke, S.T. Hedetniemi and R.C. Laskar, Fractional packings, coverings and irredundance in graphs, Congr. Numer. 66:227-238, 1988.

R. Laskar and S.T. Hedetniemi, On irredundance, dimension and rank of posets, Graph Theory and its Applications: East and West, Proc. First China-U.S.A. Internat. Graph Theory Conf., Ann. New York Acad. Sci. 576:235-240, 1989.

J. Lalani, R. Laskar and S.T. Hedetniemi, Graphs and posets: some common parameters, Congr. Numer. 71:205-216, 1990.

S.M. Hedetniemi, S.T. Hedetniemi and D.P. Jacobs, Private domination: theory and algorithms, Congr. Numer. 79:147-157, 1990.

G.S. Domke, S.T. Hedetniemi, R.C. Laskar and G. Fricke, Relationships between integer and fractional parameters of graphs, Proc. Sixth Quadrennial Conf. on the Theory and Applications of Graphs, Western Michigan Univ., Y. Alavi, G. Chartrand, O. Oellermann and A. Schwenk, Eds., Graph Theory, Combinatorics and Applications 1:371-387, Wiley Interscience Publ., 1991.

A. McRae and S.T. Hedetniemi, Finding n-independent dominating sets, Congr. Numer. 85:219-234, 1991.

G.H. Fricke, S.M. Hedetniemi, S.T. Hedetniemi, A.A. McRae, C.K. Wallis, M.S. Jacobson, W.W. Martin and W.D. Weakley, Combinatorial problems on chessboards: a brief survey, Proc. Seventh Quadrennial Internat. Conf. on the Theory and Applications of Graphs, Y. Alavi and A. Schwenk, Eds., Graph Theory, Combinatorics and Algorithms 1, pp. 507-528, Wiley, 1995.

J. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination in graphs, Proc. Seventh Quadrennial Internat. Conf. on the Theory and Applications of Graphs, Y. Alavi and A. Schwenk, Eds., Graph Theory, Combinatorics and Algorithms 1:311-322, Wiley, 1995.

S.M. Hedetniemi, S.T. Hedetniemi, R. Laskar, A. McRae and A. Majumdar, Domination, independence and irredundance in total graphs: a brief survey, Proc. Seventh Quadrennial Internat. Conf. on the Theory and Applications of Graphs, Y. Alavi and A. Schwenk, Eds., Graph Theory, Combinatorics and Algorithms 1:671-684, Wiley, 1995.

I.D. Sanders and S.T. Hedetniemi, Teaching introductory computer science: a comparison of two institutions, Proc. 28th SACLA Conf., Stellenbosch, South Africa, pp. 127-131, 1998.

S. Hedetniemi, R. Jamison and D. Rall, Equal unions of maximal independent sets in bipartite graphs, Congr. Numer., 141:185-190, 1999.

J.R.S. Blair, S.M. Hedetniemi, S.T. Hedetniemi and D.P. Jacobs, Self-stabilizing maximum matchings, Congr. Numer., 153:151-159, 2001.

S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, Fault tolerant distributed coloring algorithms that stabilize in linear time, Proc. IEEE IPDPS-2002 Workshop on Advances in Parallel and Distributed Computational Models, Orlando, FL, April, pp. 1-5, 2002.

O. Favaron, G. Fricke, W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, P. Kristiansen, R.C. Laskar and D. Skaggs, Offensive alliances in graphs, Proc. 17th Internat. Symp. Comput. Inform. Sci.,I. Cicekli, N.K. Cicekli and E. Gelenbe, Eds., ISCIS XVII, October 28-30, 2002, Orlando, FL, USA, CRC Press, pp. 298-302, 2002.

T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Global defensive alliances, ibid, pp. 303-307, 2002.

P. Kristiansen, S.M. Hedetniemi and S.T. Hedetniemi, Introduction to alliances in graphs, ibid, pp. 308-312, 2002.

S. Balasubramanian, J. Farr, K. Bernasconi, R. Laskar, J. Villalpondo, K. Hutson, G. Stevens, M. Gairing and S.T. Hedetniemi, Gallai theorems involving domination parameters, Congr. Numer., 157:149-157, 2002.

M. Gairing, S.T. Hedetniemi, P. Kristiansen and A.A. McRae, Self-stabilizing algorithms for {k}-domination, Proc. Sixth Symp. on Self-Stabilization (SSS 2003), San Francisco, CA, Springer, LNCS 2074:49-60, 2003.

W. Goddard, S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, A self-stabilizing distributed algorithm for minimal total domination in an arbitrary system graph, Proc. Eighth IPDPS Workshop on Formal Methods for Parallel Programming: Theory and Applications, Nice, France, April 22-26, 2003.

W. Goddard, S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks, Proc. Fifth IPDPS Workshop on Advances in Parallel and Distributed Computational Models, Nice, France, April 22-26, 2003.

W. Goddard, S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, A robust distributed generalized matching protocol that stabilizes in linear time, Proc. ICDCS Internat. Workshop on Mobile Distributed Computing (MDC03), Rhode Island, May 19-22, 2003.

W. Goddard, S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, Self-stabilizing distributed algorithm for strong matching in a system graph, T.M. Pinkston and V.K. Prasanna, Eds., HiPC 2003, Springer-Verlag, LNCS 2913:66-73, 2003.

Z. Xu, S.T. Hedetniemi, W. Goddard and P.K. Srimani, A synchronous self-stabilizing minimal dominating protocol in an arbitrary network graph, Proc. 5th Internat. Workshop on Distributed Computing (IWDC2003), Springer-Verlag, LNCS 2918:26-32, 2003.

W. Goddard, S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, Fault tolerant algorithms for orderings and colorings, Proc. IPDPS Workshop on Advances in Parallel and Distributed Computational Models (APDCM04), Santa Fe, New Mexico, April, 2004.

R.C. Brigham, R.D. Dutton and S.T. Hedetniemi, A sharp lower bound on the powerful alliance number of Cm x Cn, Congr. Numer. 167:57-63, 2004.

W. Goddard, S. Hedetniemi, D. Jacobs and V. Trevisan, Distance-k information in self-stabilizing algorithms, 13th Colloq. on Structural Information and Communication Complexity (SIROCCO), (Chester, UK, 2006), LNCS 4056:349-356, 2006.

W. Goddard, S.T. Hedetniemi and Z. Shi, An anonymous self-stabilizing algorithm for 1-maximal matching in trees, Proc. 2006 Internat. Conf. Parallel and Distributed Processing Techniques and Applications (PDPTA'06), Las Vegas, USA Vol. II:797-803, 2006.

W. Goddard, S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani, Anonymous daemon conversion in self-stabilizing algorithms by randomization in constant space, ICDN 2008, LNCS 4904:182-190, 2008.

S.M. Hedetniemi, S.T. Hedetniemi, R.C. Laskar, L. Markus and P.J. Slater, Disjoint dominating sets in graphs, Proc. Internat. Conf. Discrete Math., ICDM 2006 7:87-100, Ramanujan Math. Soc., Lecture Notes Series in Mathematics, 2008.

Technical Reports

S. Hedetniemi, Variants of Thatcher's algorithm for constructing pulsers, Univ. of Michigan Tech. Rept. 03105-29-T (Aug. 1964).

S. Hedetniemi, Homomorphisms of graphs, Univ. of Michigan Tech. Rept. 03105-42-T (Dec. 1965).

S. Hedetniemi, Homomorphisms of graphs and automata, Univ. of Michigan Tech. Rept. 03105-44-T (Jul. 1966).

S. Hedetniemi, Some interpolation theorems for partitions of graphs, Univ. of Michigan Tech. Rept. 03105-47-T (Mar. 1967).

S. Hedetniemi, A counterexample to a conjecture of Weeg, Dept. of Computer Science, Univ. of Iowa, Tech. Rept. 68-72 (1968).

S. Hedetniemi, What is a decomposition theory of automata?, THEMIS Project. Univ. of Iowa, Tech. Rept. 34 (Nov. 1970).

S. Hedetniemi and O. Costich, Pushdown erasers and generators, THEMIS Project, Univ. of Iowa, Tech. Rept. 48 (Nov. 1971).

T. Beyer, S. Hedetniemi and S. Mitchell, Shortest paths in trees, Dept. of Computer and Information Science, Univ. of Oregon, Tech. Rept. CS-TR-77-6 (1977).

E.J. Cockayne and S.T. Hedetniemi, A conjecture concerning broadcasting in m-dimensional grid graphs, Dept of Computer and Information Science, Univ. of Oregon, Tech. Rept. CS-TR-78-14 (1978).

S. Hedetniemi and S. Mitchell, Centers of recursive graphs, Dept. of Computer and Information Science, Univ. of Oregon, Tech. Rept. CS-TR-79-11 (1979).

S.M. Hedetniemi and S.T. Hedetniemi, Broadcasting by decomposing trees into paths of bounded length, Dept. of Computer and Information Science, Univ. of Oregon, Tech. Rept CS-TR-79-16 (1979).

E.J. Cockayne, S.T. Hedetniemi and S.L. Mitchell, Linear algorithms for mean distances in trees and unicyclic graphs, Dept. of Computer and Information Science, Univ. of Oregon, Tech. Rept. CS-TR-79-22 (1979).

T. Beyer, S.M. Hedetniemi and S.T. Hedetniemi, A linear algorithm for finding the center of a unicyclic graph, Dept. of Computer and Information Science, Univ. of Oregon, Tech. Rept. CIS-TR-80-12 (1980).

S.M. Hedetniemi and S.T. Hedetniemi, A note on the complexity of vertex and edge partition problems for graphs, Dept. of Computer and Information Science, Univ. of Oregon, Tech. Rept. CIS-TR-80-17 (1980).

J. Pfaff, R. Laskar and S.T. Hedetniemi, NP-completeness of total and connected domination, and irredundance for bipartite graphs, Dept. Mathematical Sciences, Clemson University, Tech. Rept. 428 (July 1983).

J. Pfaff, R. Laskar and S.T. Hedetniemi, A linear algorithm for finding a minimum dominating set in a cactus, Dept. Mathematical Sciences, Clemson University, Tech. Rept. URI-001 (1985).

S.M. Hedetniemi, S.T. Hedetniemi and T. Wimer, Linear time resource allocation algorithms for trees, Dept. Mathematical Sciences, Clemson University, Tech. Rept. URI-014 (1986).

S.T. Hedetniemi, D.P. Jacobs, R. Laskar and D. Pillone, Open perfect neighborhoods in graphs, Dept. Computer Science, Clemson University, (1997).

INVITED PRESENTATIONS

Invited Colloquia

Aalborg University, Aalborg, Denmark

American University Cairo, Egypt

Auburn University, AL

Brigham Young University, Provo, UT

California State University, San Marcos

Clemson University, SC

College of William & Mary, VA

Converse College, SC

East Tennessee State University

Georgia State University

Gustavus Adolphus College, MN

Indiana University-Purdue University, Ft. Wayne

Iowa State University

Longwood College, VA

Michigan State University

Old Dominion University

Oregon State University

Pennsylvania State University

Royal Institute of Technology, Stockholm, Sweden

Simon Fraser University, Burnaby, B.C., Canada

St. Mary's College of Maryland

SUNY at Buffalo, NY

Universite de Paris-Sud, Orsay, France

University of Alabama in Huntsville

University of Alberta, Edmonton, Canada

University of Bergen, Norway

University of Central Florida

University of Iowa

University of Kentucky

University of Louisville, KY

University of Missouri, Rolla

University of Missouri, St. Louis

University of North Carolina at Wilmington

University of Oregon

University of Saskatchewan, Saskatoon, Canada

University of South Carolina

University of South Carolina Spartanburg

University of Texas, Austin

University of Toronto, Ontario, Canada

University of Victoria, B.C., Canada

University of Virginia

Virginia Polytechnic University

Wake Forest University, NC

Washington State University

Wayne State University, MI

West Virginia University

Western Carolina University

Western Michigan University

Wright State University, OH

Keynote/Principal Speaker

DIMACS Conference on Concepts of Domination in Graphs and Directed Graphs, Rutgers University, July, 2000.

29th Midwestern Graph Theory Conference, Michigan State University, May, 1998.

Third North Carolina Mini-Conference on Graph Theory, Combinatorics and Computing, Appalachian State University, April, 1998.

Northern Michigan Mathematical Association Conference, Northern Michigan University, Marquette, MI, October, 1996.

International Workshop on Graph Theory and Communication Networks (IWGTCN), University of Oregon, July, 1996.

Seventh Cumberland Conference on Graph Theory and Computing, University of Alabama in Huntsville, May, 1994.

Michigan Section - MAA Upper Peninsular Regional Meeting, Northern Michigan University, Marquette, October, 1991.

Midwestern Graph Theory Conference, Wright State University. Dayton, OH, November, 1987.

Invited Conference Speaker

DIMACS Conference on Distance and Centrality Concepts in Graphs, Rutgers University, July 2000

Ninth Quadrennial International Conference in Graph Theory, Combinatorics, Algorithms, and Applications, June, 2000.

Thirteenth Cumberland Conference on Graph Theory, Combinatorics and Computing, University of Alabama in Huntsville, May, 2000.

Twelfth Cumberland Conference on Combinatorics, Graph Theory and Computing, University of Louisville, May, 1999.

Symposium in Graph Theory in Honour of Preben Dahl Vestergaard, Aalborg University, Denmark, January, 1999.

AMS Regional Conference, Lexington, KY, March, 1995.

Seventh Quadrennial International Conference on the Theory and Applications of Graphs, Western Michigan University, June, 1992.

Fifth Cumberland Conference on Discrete Mathematics, Emory University, Atlanta, May, 1991.

Sixth International Las Cruces Symposium on Graph Theory in Computer Science and Chemistry, New Mexico State University, March, 1991.

Fourth Cumberland Conference, University of Louisville, Louisville, KY, May, 1990.

CORS/ORSA/TIMS Conference, Vancouver, B.C., May, 1989.

Fall National ORSA/TIMS Conference, St. Louis, MO, October, 1987.

AMS 1987 Joint Summer Research Conference on Graphs and Algorithms, University of Colorado, Boulder, July, 1987.

First Cumberland Conference on Graph Algorithms and Combinatorics,, Tennessee Technological University, April, 1987.

Fifth Quadrennial Conf. on the Theory and Applications of Graphs, Western Michigan University, Kalamazoo, MI, 1986.

250th Anniversary Conference on Graph Theory, Indiana University- Purdue University, Ft. Wayne, IN, March, 1986.

Combinatoria Conference, Sundance, UT, August, 1985.

NSF/CBMS Conference: Applications of Combinatorics and Graph Theory to Computer Science, University of Alabama in Huntsville, June, 1985.

Southeast Regional Conference on Problem Solving, Asheville, NC, April, 1985.

Fifth Quadrennial International Conference on the Theory and Applications of Graphs with special emphasis on Algorithms and Computer Science Applications, Western Michigan University, June, 1984.

Second West Coast Conference on Combinatorics, Graph Theory, and Computing, University of Oregon, June, 1983.

Fourth Quadrennial Conf. on the Theory and Applications of Graphs, Western Michigan University, Kalamazoo, MI, June, 1982.

Northern California Mathematical Association Conference, Humboldt State University, Arcata, CA, November, 1981.

SIAM National Conference, Colorado Springs, CO, November, 1980

Third Quadrennial Conf. on the Theory and Applications of Graphs, Western Michigan University, Kalamazoo, MI, June, 1978.

Conference on Graph Theory and Applications, Western Michigan University, May, 1972.

First New York City Graph Theory Conference, St. John's University, June, 1970.

Conference on Graph Theory, Western Michigan University, November, 1968.

NATO Graph Theory Conference, Varenna, Italy, 1966.

SPONSORED RESEARCH

University of Michigan

NSF International Travel Grant, August, 1966

(approx.) $1,500

 

University of Iowa

ONR Project THEMIS

(approx.) $220,000, 1969-1970

(approx.) $180,000, 1970-1971

(with R. Oehmke, E. Madison, A.C. Fleck and J. Robinson)

 

University of Oregon

NSF Grant: Towards a Theory of Linear Recursive Data Structures

$24,164, June 1979 - August 1980

$51,000, October 1981 - January 1983

(with S.M. Hedetniemi)

 

NSF Grant: Information Dissemination in Communication Networks

$41,000, August 1979 - August 1981

(with A. Farley, S.M. Hedetniemi, A. Proskuroswki and P. Wang)

 

NSF Grant: Using Microcomputers in Undergraduate Science Education

$273,153, September 1979 - September 1982

(with T. Beyer, R. Haller, S.M. Hedetniemi and D. Moursund)

 

Clemson University

NSF Grant: Towards a Theory of Linear Recursive Data Structures

(Transfer to Clemson University)

$44,243, May 1983 - May 1985

(with S.M. Hedetniemi)

 

ONR Contract: A Theory of Linear Computation

$57,000, June 1986 - June 1987

(with R. Laskar and T. Wimer)

 

ONR Contract: The Clemson University Research Initiative Program in Discrete Mathematics and Computational Analysis

$1,500.000, September 1986 - August 1989

(with W.R. Verry, C.R. Johnson, D.D. Warner, D.R. Shier, J.P. Jarvis, R.C. Laskar, R.E. Fennell, R.E. Haymond, J.A. Reneke, T.G. Proctor and J.R. Brannan)

 

ONR/NSA Contracts: The Clemson mini-Conferences on Discrete Mathematics

(approx.)$4,000-$8,000/yr, 1986-2000

(with R.C. Laskar)

 

NSF Grant: Computing equipment

$500.000, 1997

(with R.M. Geist, R.J. Schalkoff, D.M. Dawson,...)

NSF Grant: ITR: Self-Stabilizing Networking Protocols for Distributed Systems

$394,000, September15,2002 - September 15, 2005.

GRADUATE STUDENT SUPERVISION

Doctoral Graduates

Curtis J. Cook, "Graphs associated with (0,1) arrays," Dept. Computer Science, University of Iowa, 1970.

Peter J. Slater, "Classifying n-connected graphs," Dept. Mathematics, University of Iowa, 1973.

Frances Van Scoy, "Parallel algorithms in cellular spaces," Dept. Applied Math. & Computer Science, Univ. Virginia, 1976.

Sandra L. Mitchell, "Algorithms on trees and maximal outerplanar graphs: design, complexity analysis and data structures study," Dept. Applied Math. & Computer Science, Univ. Virginia, 1977.

Thomas V. Wimer, "Linear algorithms on k-terminal graphs," Dept. Computer Science, Clemson Univ., 1987.

Gayla S. Domke, "Variations of colorings, coverings and packings of graphs," Dept. Mathematical Sciences, Clemson Univ., 1987, (joint Supervisor with Prof. R.C. Laskar).

Eleanor O. Hare, "Algorithms for grids and grid-like graphs," Dept. Computer Science, Clemson Univ., 1989.

Chandrasekharan Narayanan, "Fast parallel algorithms and enumeration techniques for partial k-trees," Dept. Mathematical Sciences, Clemson Univ., 1989.

Aniket Majumdar, "Neighborhood hypergraphs: a framework for covering and packing parameters in graphs," Dept. Mathematical Sciences, Clemson Univ., 1991, (joint Supervisor with Prof. R.C. Laskar).

Alice A. McRae, "Generalizing NP-completeness proofs for bipartite and chordal graphs," Dept. Computer Science, Clemson Univ., 1994.

Frederick C. Harris, Jr., "Parallel computation of Steiner minimal trees," Dept. Computer Science, Clemson Univ., 1994.

Lindsay H. Jamieson, "Algorithms and complexity for alliances and weighted alliances of various types," School of Computing, Clemson Univ., 2007.

Alan C. Jamieson, "Linear-time algorithms for edge-based problems," School of Computing, Clemson Univ., 2007.

Jason Lewis, "Vertex-edged and edge-vertex parameters in graphs," School of Computing, Clemson Univ., 2007.

Masters Graduates

David C. Barnhart , II, "Polling in trees: an analysis of a special case problem," Clemson Univ., 1988.

Mary Lejune High, "Graph coloring: an overview of algorithms," Clemson Univ.

Ohtani Kazunori, "Generalized coloring and perfection in powers of trees," Clemson Univ.

Albert E. Myers, "An empirical study involving the compression of the problem space with an NP-Complete problem," Clemson Univ.

Shahin Razavi, Clemson Univ.

Keith Smith, "Linear-time computability of subgraph problems on series-parallel graphs," Clemson Univ.

Alan Ward, "A linear program for parsing series-parallel graphs and its application in solving the domination problem for series-parallel graphs," Clemson Univ.

Tao Ding, "A comparison of heuristic algorithms for the Minimum Latency Problem (MLP)," Clemson Univ., May 2000.

Quan Li, "The Minimum Latency Problem," Clemson Univ., May 2000.

Martin Gairing, "A self-stabilizing algorithm for maximal k-dependent set," Clemson Univ., December 2001.

Amrita Thakur, "A case study of job shop scheduling," Clemson Univ., August 2002.

Kranti Vijay Dugiraala, "Genetic algorithms for physical mapping of DNA using unique probes," Clemson Univ., November 2003.

James Huff, "Capacity domination in graphs," Clemson Univ., December 2005.

Abbas Amirabadi, "Values of total domination numbers and connected domination numbers in queen graph," Clemson Univ., December 2005.

Neil Harmon, "Higher-order genetic algorithms," Clemson Univ., April 2006.

TEACHING

Courses taught at Clemson University

Introduction to Computer Science (101,102)

Programming Methodology (210)

Introduction to Data Structures (240)

Algorithms and Data Structures (340)

Foundations of Computer Science (350)

Peripherals and File Design (360)

Systems Analysis (371)

Introduction to Software Development (372)

Design and Implementation of Programming Languages (428)

Theory of Computation (450/650)

Software Development Methodology (472)

Artificial Intelligence (810)

Analysis of Algorithms (840)

Foundations of Theoretical Computer Science (839/859)

Algorithms Seminar (957)

Parallel Algorithms Seminar (957)

PROFESSIONAL RECOGNITION

University of Oregon Summer Research Award, 1977

 

University of Victoria, Visiting Research Appointment, 1976-77

 

Approximately 40 university colloquium presentations

 

Approximately 40 invited conference presentations

 

Invited lecture series:

Department of Computer Science Oregon State University, Spring, 1976.

Department of Computer Science, University of Missouri, Rolla Spring, 1980.

Department of Mathematics, Indiana University-Purdue University, Ft. Wayne, IN, Scholor-in-Residence, June, 1991.

 

Five keynote presentations at conferences

 

The Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 31, October 1999, Papers in Honour of Stephen T. Hedetniemi, P.J. Slater, Editor.

 

Clemson University, Board of Trustees, Award for Faculty Excellence, April 6, 2000

 

UNIVERSITY AND PUBLIC SERVICE

Computing Consultant: City of Charlottesville, Virginia.

 

Book Reviewer: Prentice-Hall, West Publ., Addison-Wesley, Benjamin-Cummings.

 

Research Consultant: Department of Mathematics, University of Victoria.

 

External Ph.D. Examiner: University of Toronto, Toronto, Ontario; University of Alberta, Edmonton, Alberta; Rutgers University, Piscataway, NJ; Western Michigan University, Kalamazoo, MI; Mangalore University, Karnataka, India; University of Victoria, Victoria, B.C., University of Stellenbosch, South Africa.

 

Research Proposal Reviewer: Louisiana Board of Regents; National Science Foundation; Canadian National Research Council; South African Foundation for Research; University of Hong Kong.

 

ETS Consultant: Computer Science Advanced Placement Exam.

 

Computing Accreditation Program Evaluator and Team Chair: Computer Science Accreditation Commission of CSAB and Computing Accreditation Commission of ABET: 1986, 1987, 1988, 1990, 1992, 1993, 1994, 1995, 1996, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008.

Executive Committee: Computing Accreditation Commission, 2002, 2003, 2004, 2005.

 

Computing Accreditation Consultant: Southern Utah University; Roosevelt University; University of Central Florida; Edinboro University of Pennsylvania; University of Georgia.

 

Program Reviewer: Department of Computer Science, University of Georgia; Department of Computer Science, University of Nevada, Reno; Department of Mathematics, Western Carolina University, Cullowhee, NC; Department of Mathematics and Computer Science, Wake Forest University, Winston Salem, NC; Department of Computer Science, Willamette University, Salem, OR; Department of Computer Science, U.S. Naval Academy, Annapolis, MD; Department of Computer Science, University of Massachusetts Boston.

 

Co-organizer and Co-host: Clemson mini-Conference on Discrete Mathematics, with Professor Renu Laskar, Department of Mathematical Sciences, 1986-2006, with support from ONR, NSA and Clemson University, College of Engineering and Science, and Departments of Mathematical Sciences and Computer Science.

 

Referee: Journal of Algorithms; SIAM Journal of Computing; Discrete Mathematics; Discrete Applied Mathematics; NETWORKS; Ars Combinatoria; Australasian Journal of Combinatorics; Computers and Mathematics with Applications; Information Processing Letters; Bulletin of the Institute of Combinatorics and Its Applications; Journal of Combinatorial Mathematics and Combinatorial Computing; Journal of Combinatorial Theory Series B; Journal of Combinatorics, Information and Systems Sciences; Discussiones Mathematicae Graph Theory; Tamkang Journal of Mathematics.

 

Promotion and Tenure Reviewer: Western Michigan University; Michigan State University; Wellesley College; Bowdoin College; RPI; St. Mary's University, Nova Scotia; Old Dominion University; New Jersey Institute of Technology; Southwest Texas State University; Oregon State University; Virginia Institute of Technology; Oakland University; University of Michigan Dearborn; U.S. Military Academy; Connecticut College; Indiana University Purdue University, Ft. Wayne; University of South Carolina; University of Alabama at Birmingham.

 

University, College, School and Department Committees: University: Faculty Senate (brief term), Commission on Higher Education Graduate Program Review Committee; College: Associate Dean Search and Screening Committee, Alumni Professor Selection Committee, Teaching Effectiveness Committee; Department and School: Promotion and Tenure Committee, Post Tenure Review Committee, Advisory Committee, Colloquium Committee, Ph.D. Exam Committee, Graduate Affairs Committee, Faculty Search Committee, Assessment Committee.