Summary
Jean Vuillemin is a French computer scientist known for his work in data structures and parallel computing. He is a professor of computer science at the École normale supérieure (Paris).[1]
Contributions edit
Vuillemin invented the binomial heap[2][B] and Cartesian tree data structures.[3][C] With Ron Rivest, he proved the Aanderaa–Rosenberg conjecture, according to which any deterministic algorithm that tests a nontrivial monotone property of graphs, using queries that test whether pairs of vertices are adjacent, must perform a quadratic number of adjacency queries.[4][A]
In the 1980s, Vuillemin was the director of a project to develop a workstation using VLSI technology, under which the Le Lisp programming language was developed.[5] With Franco P. Preparata, he also introduced the cube-connected cycles as a network topology in parallel computing.[6][D]
Education and career edit
Vuillemin earned an engineering degree at the École Polytechnique in 1968, a doctorate (troisième cycle) at the University of Paris in 1969, a Ph.D. from Stanford University in 1972 under the supervision of Zohar Manna, and a state doctorate from Paris Diderot University in 1974.[1][7]
He became an assistant professor at the University of California, Berkeley in 1974, but then returned to France in 1975 for a position at the University of Paris-Sud. He moved to the École Polytechnique in 1982, to the Ecole de Management Léonard De Vinci in 1994, and to the École normale supérieure in 1997.[1]
Selected publications edit
| A. | Rivest, Ronald L.; Vuillemin, Jean (1975), "A generalization and proof of the Aanderaa–Rosenberg conjecture", Proc. 7th ACM Symposium on Theory of Computing, pp. 6–11, CiteSeerX 10.1.1.309.7236, doi:10.1145/800116.803747
|
| B. | Vuillemin, Jean (April 1978), "A data structure for manipulating priority queues", Communications of the ACM, 21 (4): 309–314, CiteSeerX 10.1.1.309.9090, doi:10.1145/359460.359478
|
| C. | Vuillemin, Jean (1980), "A unifying look at data structures", Communications of the ACM, 23 (4): 229–239, doi:10.1145/358841.358852
|
| D. | Preparata, Franco P.; Vuillemin, Jean (1981), "The cube-connected cycles: a versatile network for parallel computation", Communications of the ACM, 24 (5): 300–309, doi:10.1145/358645.358660, hdl:2142/74219
|
References edit
- ^ a b c Biographie, retrieved 2019-10-19
- ^ Hinze, Ralf (January 1999), "Explaining binomial heaps", Journal of Functional Programming, 9 (1): 93–104, doi:10.1017/s0956796899003317
- ^ Weiss, Mark Allen (December 1994), "Linear-time construction of treaps and Cartesian trees", Information Processing Letters, 52 (5): 253–257, doi:10.1016/0020-0190(94)00150-2
- ^ Tarjan, Robert Endre (1978), "Complexity of combinatorial algorithms", SIAM Review, 20 (3): 457–491, doi:10.1137/1020067, MR 0483708
- ^ Chailloux, J.; Devin, M.; Hullot, J. M. (1984), Le_Lisp, a portable and efficient Lisp system, Report RR-0319, INRIA
- ^ Borodin, A.; Hopcroft, J. E. (1982), "Routing, merging and sorting on parallel models of computation", Proceedings of the Fourteenth annual ACM Symposium on Theory of Computing (STOC '82), doi:10.1145/800070.802209
- ^ Jean Vuillemin at the Mathematics Genealogy Project
External links edit
- Home page