I am writing a survey article on community structure in networks, and part of my hard work in doing this is to look up classical algorithms from the computer science and other literatures that give a prehistory to its modern descendants that are being used in network science.
One of the things that I looked up in the process was of course the Kernighan-Lin algorithm for graph partitioning. In the process, I became extremely impressed with Brian Kernighan for several reasons. For one, it looks like he devised this algorithm as part of his Ph.D. thesis. At around the same time, he and Lin devised an important algorithm for the traveling salesman problem (this is usually called the Lin-Kernighan algorithm. Then I looked further and found out that he is the one who devised the ubiquitous "Hello, world" paradigm, co-authored the first book on the C programming language, and contributed fundamentally to Unix from its inception. (His wikipedia entry credits him with coming up with a pun leading to Unix's name. That statement seems more speculative, so I'll just report that this is stated in the entry. Mabye Lemming or Zifnab might be able to comment on this?) The only thing that would be cooler would be if he had coauthored The Mythical Man Month.
No comments:
Post a Comment