Not to be confused with French mycologist Jean Paul Vuillemin (1861–1932).

Jean Vuillemin (born May 22, 1947, Pontarlier, France, died May 25, 2026, Paris, France) was a computer scientist known for his work in data structures and parallel computing. He was a professor of computer science at the École normale supérieure (Paris).[1]

He was born of Suzanne Vuillemin (née Pagnier) and French philosopher Jules Vuillemin.[2]

Contributions

Vuillemin invented the binomial heap[3]: B and Cartesian tree data structures.[4]: 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.[5]: 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.[6] With Franco P. Preparata, he also introduced the cube-connected cycles as a network topology in parallel computing.[7]: D

Education and career

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][8]

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]

References

  1. ^ "Biographie", retrieved 2019-10-19
  2. ^ Vuillemin, Jules (1991), "Ma Vie En Bref", Causality, Method, and Modality, Dordrecht: Springer Netherlands, pp. 1–4, ISBN 978-94-010-5479-9, retrieved 2026-03-18
  3. ^ Hinze, Ralf (January 1999), "Explaining binomial heaps", Journal of Functional Programming. 9 (1): 93–104, doi:10.1017/s0956796899003317
  4. ^ 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
  5. ^ Tarjan, Robert Endre (1978), "Complexity of combinatorial algorithms", SIAM Review. 20 (3): 457–491, doi:10.1137/1020067. MR 483708
  6. ^ Chailloux, J.; Devin, M.; Hullot, J. M. (1984), "Le_Lisp, a portable and efficient Lisp system", Report RR-0319, INRIA
  7. ^ 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), pp. 338–344, doi:10.1145/800070.802209. ISBN 0-89791-070-2
  8. ^