Jump to content

Derek Corneil

Edit links
From Wikipedia, the free encyclopedia
Derek G. Corneil
NationalityCanadian
Education
Scientific career
Fields
InstitutionsUniversity of Toronto
Thesis Graph Isomorphism  (1968)
Doctoral advisorCalvin Gotlieb
Doctoral students

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

[edit]

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. His 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 took a summer job operating the UNIVAC Mark II at the 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-doctoral supervisor was Jaap Seidel.) It was during this time that Corneil became interested in graph theory. 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] Corneil held many positions at the University of Toronto, including 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 (September to December 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 Université de Grenoble and the Université de Montpellier.

Work

[edit]

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 co-authors. These papers include:

A proof that recognizing graphs of small treewidth is NP-complete,[5]
The discovery of the cotree representation for cographs and of fast recognition algorithms for cographs,[6][7]
Generating algorithms for graph isomorphism.[8][9]
Algorithmic and structural properties of complement reducible graphs.[10]
Properties of asteroidal triple-free graphs.[11]
An algorithm to solve the problem of determining whether a graph is a partial graph of a k-tree.[12]
Results addressing graph theoretic, algorithmic, and complexity issues with regard to tree spanners.[13]
An explanation of the relationship between tree width and clique-width.[14]
Determining the diameter of restricted graph families.[15]
Outlining the structure of trapezoid graphs.[16]

As a professor emeritus, Corneil still does research and is also an editor of several publications such as Ars Combinatoria and SIAM Monographs on Discrete Mathematics and Applications.

Awards

[edit]

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

References

[edit]
  1. ^ "Derek Corneil: Renowned and Esteemed Computer Science Professor Emeritus University of Toronto - Canadian IT Manager's Blog - Site Home - TechNet Blogs". Archived from the original on 2011-06-23. Retrieved 2012-02-19.
  2. ^ a b Biography, University of Toronto. Retrieved 1/8 February 2012.
  3. ^ Derek Gordon Corneil at the Mathematics Genealogy Project
  4. ^ "Derek Corneil: Retiring after 40 years with DCS" (PDF), @DCS, 1 (3), University of Toronto Department of Computer Science: 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 0881187.
  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 0619603
  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 0807891.
  8. ^ Corneil, D. G.; Gotlieb, C. C. (1970), "An efficient algorithm for graph isomorphism", Journal of the ACM, 17: 51–64, CiteSeerX 10.1.1.453.3730, doi:10.1145/321556.321562, MR 0278977, S2CID 207720001
  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. ^ 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.
  11. ^ Corneil, Derek G.; Olariu, Stephan; Stewart, Lorna (1997). "Asteroidal Triple-Free Graphs". SIAM Journal on Discrete Mathematics. 10 (3): 399–430. doi:10.1137/S0895480193250125.
  12. ^ 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.
  13. ^ Cai, Leizhen; Corneil, Derek G. (1995). "Tree Spanners". SIAM Journal on Discrete Mathematics. 8 (3): 359–387. doi:10.1137/S0895480192237403.
  14. ^ Corneil, Derek G.; Rotics, Udi (2005). "On the Relationship Between Clique-Width and Treewidth". SIAM Journal on Computing. 34 (4): 825–847. doi:10.1137/S0097539701385351.
  15. ^ Corneil, Derek G.; Dragan, Feodor F.; Habib, Michel; Paul, Christophe (2001). "Diameter determination on restricted graph families" (PDF). Discrete Applied Mathematics. 113 (2–3): 143–166. doi:10.1016/S0166-218X(00)00281-X.
  16. ^ Mertzios, George B.; Corneil, Derek G. (2011). "Vertex splitting and the recognition of trapezoid graphs" (PDF). Discrete Applied Mathematics. 159 (11): 1131–1147. doi:10.1016/j.dam.2011.03.023.
  17. ^ Fields Institute Fellows. Retrieved 18 February 2012.
[edit]
Retrieved from "http://en.wiki.x.io/w/index.php?title=Derek_Corneil&oldid=1187370523"