Derek Corneil

Derek G. Corneil
Born (1942-12-27) 27 December 1942
Quebec
Main interests
 Graph Theory
Computer Science

Derek Gordon Corneil is a Canadian mathematician and computer scientist, a professor emeritus of Computer Science at the University of Toronto, and an expert in graph algorithms and Graph Theory.

Life

When he was leaving high school, Corneil was told by his English teacher that doing a degree in Mathematics and Physics was a bad idea, and that the best he could hope for was to go to a technical college. The Quebec native’s interest in Computer Science began when, as an undergraduate student at Queens College, he heard that a computer was purchased by the London life insurance company in London, Ontario where his father worked. As a freshman he got a summer job operating the UNIVAC Mark II at said company. One of his main responsibilities was to operate a printer. An opportunity for a programming job with the company sponsoring his college scholarship appeared soon after. It was a chance that Corneil jumped at after being denied a similar position at London Life. There was an initial mix-up at his job as his overseer thought that he knew how to program the UNIVAC Mark II, and so he would easily transition to doing the same for the company's newly acquired IBM 1401 machine. However, Corneil did not have the assumed programming background. Thus, in the two week window that Corneil had been given to learn how to grasp programming the IBM 1401, he learned how to write code from scratch by relying heavily on the instruction manual. This experience pushed him further on his way as did a number of projects he worked on in that position later on.[1]

Corneil went on to earn a bachelor's degree in mathematics and physics from Queen's University in 1964. Initially he had planned to do his graduate studies before becoming a high school teacher, but his acceptance into the brand new graduate program in Computer Science at the University of Toronto changed that. At the University of Toronto, Corneil earned a master's degree and then in 1968 a doctorate in computer science under the supervision of Calvin Gotlieb.[2][3] (His post-doc supervisor was Jaap Seidel.) It was during this time that Corneil's interest in Graph Theory began to blossom. He and Gotlieb eventually became good friends. After postdoctoral studies at the Eindhoven University of Technology, Corneil returned to Toronto as a faculty member in 1970.[2] Before his retirement in 2010,[4] Dr. Corneil held many positions at the university of Toronto. These include Department Chair of the Computer Science department (July 1985 to June 1990), Director of Research Initiatives of the Faculty of Arts and Science (July 1991 to March 1998), and Acting Vice President of Research and International Relations (Sept. to Dec. 1993). During his time as a professor, he was also a visiting professor at universities such as the University of British Columbia, Simon Fraser University the Universite de Grenoble and the Universite de Montpellier.

Work

Dr. Corneil did his research in algorithmic graph theory and graph theory in general. He has overseen 49 theses and published over 100 papers on his own or with other co-authors. These papers include:

1) A proof that recognizing graphs of small treewidth is NP-complete,[5]

2) The discovery of the cotree representation for cographs and of fast recognition algorithms for cographs,[6][7]

3) Generating algorithms for graph isomorphism.[8][9]

4) Algorithmic and structural properties of complement reducible graphs.[10]

5) Properties of asteroidal triple-free graphs.[11]

6) An algorithm to solve the problem of determining whether a graph is a partial graph of a k-tree.[12]

7) Results addressing graph theoretic, algorithmic, and complexity issues with regard to tree spanners.[13]

8) An explanation of the relationship between tree width and clique-width.[14]

9) Determining the diameter of restricted graph families.[15]

10) Outlining the structure of trapezoid graphs.[16]

Currently as a Professor Emeritus, Dr. Corneil still does research and also serves as an editor of several publications such as Ars Combinatoria and SIAM Monographs on Discrete Mathematics and Applications.

Awards

He was inducted as a Fields Institute Fellow in 2004.[17]

References

  1. ↑ http://blogs.technet.com/b/cdnitmanagers/archive/2011/06/13/derek-corneil-renowned-and-esteemed-computer-science-professor-emeritus-university-of-toronto.aspx
  2. 1 2 Biography, Univ. of Toronto, retrieved 2012-02-18.
  3. ↑ Derek Gordon Corneil at the Mathematics Genealogy Project
  4. ↑ "Derek Corneil: Retiring after 40 years with DCS" (PDF), @dcs, University of Toronto Department of Computer Science, 1 (3): 8, 2010.
  5. ↑ Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej (1987), "Complexity of finding embeddings in a $k$-tree", SIAM Journal on Algebraic and Discrete Methods, 8 (2): 277–284, doi:10.1137/0608024, MR 881187.
  6. ↑ Corneil, D. G.; Lerchs, H.; Burlingham, L. Stewart (1981), "Complement reducible graphs", Discrete Applied Mathematics, 3 (3): 163–174, doi:10.1016/0166-218X(81)90013-5, MR 619603.
  7. ↑ Corneil, D. G.; Perl, Y.; Stewart, L. K. (1985), "A linear recognition algorithm for cographs", SIAM Journal on Computing, 14 (4): 926–934, doi:10.1137/0214065, MR 807891.
  8. ↑ Corneil, D. G.; Gotlieb, C. C. (1970), "An efficient algorithm for graph isomorphism", Journal of the ACM, 17: 51–64, doi:10.1145/321556.321562, MR 0278977.
  9. ↑ Read, Ronald C.; Corneil, Derek G. (1977), "The graph isomorphism disease", Journal of Graph Theory, 1 (4): 339–363, doi:10.1002/jgt.3190010410, MR 0485586.
  10. ↑ "Complement reducible graphs". Discrete Applied Mathematics. 3: 163–174. doi:10.1016/0166-218X(81)90013-5.
  11. ↑ "Asteroidal Triple-Free Graphs". SIAM Journal on Discrete Mathematics. 10: 399–430. doi:10.1137/S0895480193250125.
  12. ↑ "Complexity of Finding Embeddings in a k -Tree". SIAM Journal on Algebraic Discrete Methods. 8: 277–284. doi:10.1137/0608024.
  13. ↑ "Tree Spanners". SIAM Journal on Discrete Mathematics. 8: 359–387. doi:10.1137/S0895480192237403.
  14. ↑ http://epubs.siam.org/doi/abs/10.1137/S0097539701385351
  15. ↑ "Diameter determination on restricted graph families". Discrete Applied Mathematics. 113: 143–166. doi:10.1016/S0166-218X(00)00281-X.
  16. ↑ "Vertex splitting and the recognition of trapezoid graphs". Discrete Applied Mathematics. 159: 1131–1147. doi:10.1016/j.dam.2011.03.023.
  17. ↑ Fields Institute Fellows, retrieved 2012-02-18.

External links

This article is issued from Wikipedia - version of the 7/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.