| 2005 | ICALP | Union-Find with Constant Time Deletions. | Stephen Alstrup, Inge Li Grtz, Theis Rauhe, Mikkel Thorup, Uri Zwick |
| 2003 | SODA | Labeling schemes for small distances in trees. | Stephen Alstrup, Philip Bille, Theis Rauhe |
| 2002 | FOCS | Small Induced-Universal Graphs and Compact Implicit Graph Representations. | Stephen Alstrup, Theis Rauhe |
| 2002 | SODA | Improved labeling scheme for ancestor queries. | Stephen Alstrup, Theis Rauhe |
| 2002 | SPAA | Nearest common ancestors: a survey and a new distributed algorithm. | Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe |
| 2001 | SODA | A cell probe lower bound for dynamic nearest-neighbor searching. | Stephen Alstrup, Thore Husfeldt, Theis Rauhe |
| 2001 | STOC | Optimal static range reporting in one dimension. | Stephen Alstrup, Gerth Stlting Brodal, Theis Rauhe |
| 2000 | FOCS | New Data Structures for Orthogonal Range Searching. | Stephen Alstrup, Gerth Stlting Brodal, Theis Rauhe |
| 2000 | SODA | Pattern matching in dynamic texts. | Stephen Alstrup, Gerth Stlting Brodal, Theis Rauhe |
| 1999 | STOC | Worst-Case and Amortised Optimality in Union-Find (Extended Abstract). | Stephen Alstrup, Amir M. Ben-Amram, Theis Rauhe |
| 1998 | FOCS | Marked Ancestor Problems. | Stephen Alstrup, Thore Husfeldt, Theis Rauhe |
| 1998 | FOCS | Optimal Time-Space Trade-Offs for Sorting. | Jakob Pagter, Theis Rauhe |
| 1998 | ICALP | Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Method. | Thore Husfeldt, Theis Rauhe |
| 1995 | TACAS | Mona: Monadic Second-Order Logic in Practice. | Jesper G. Henriksen, Jakob L. Jensen, Michael E. Jrgensen, Nils Klarlund, Robert Paige, Theis Rauhe, Anders Sandholm |
| 1995 | WADS | Dynamic Algorithms for the Dyck Languages. | Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, Sren Skyum |