About The Author

Jeffrey Scott Vitter (F’93) received the B.S. degree (Hons.) in mathematics from the University of Notre Dame in 1977, the Ph.D. degree in computer science from Stanford University in 1980, and an M.B.A degree from Duke University in 2002. He is currently Distinguished Professor of Computer and Information Science with the University of Mississippi, where he served as chancellor from 2016 to 2019. From 2010 to 2015, he was provost and executive vice chancellor and Roy A. Roberts Distinguished Professor at the University of Kansas. From 2008 to 2010, he was on the faculty at Texas A&M University, where he also served as a provost and executive vice president for academics. From 2002 to 2008, he was the Frederick L. Hovde Dean of Science with Purdue University. From 1993 to 2002, he held the Gilbert, Louis, and Edward Lehrman Distinguished Professorship with Duke University, where he also served as a chair of the Department of Computer Science and a co-director of Duke’s Center for Geometric and Biological Computing. From 1980 to 1992, he advanced through the faculty ranks in computer science at Brown University. He is Guggenheim Fellow and a Fellow of the ACM, AAAS, and IEEE, and he is a U.S. National Science Foundation Presidential Young Investigator and Fulbright Scholar. He has authored the book Algorithms and Data Structures for External Memory, co-authored the books Design and Analysis of Coalesced Hashingand Efficient Algorithms for MPEG Video Compression, co-edited the collections External Memory Algorithmsand Algorithm Engineering, and co-holder of patents in the areas of external sorting, prediction, and approximate data structures. His research interests span the design and analysis of algorithms, external memory algorithms, data compression, databases, compressed data structures, parallel algorithms, machine learning, random variate generation, and sampling. He has received the IBM Faculty Development Award, the ACM Recognition of Service Award (twice), and the 2009 ACM SIGMOD Test of Time Award. He has served on several boards and professional committees. He serves or has served on the editorial boards of Algorithmica, Communications of the ACM, IEEE Transactions on Computers, Theory of Computing Systems, and SIAM Journal on Computing, and has edited several special issues.

Fast Computation Of Graph Edit Distance

Measuring the similarity between two graphs is a basic operation with many applications. For example, in the fields of chemical informatics and drug design, we often need to compare the similarity of a chemical (as modeled by a labeled graph) to a known drug (as modeled by another labeled graph) in order to evaluate the