| 2001 | Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach. | Feodor F. Dragan |
| 2001 | Planarity of the 2-Level Cactus Model. | Sabine Cornelsen, Yefim Dinitz, Dorothea Wagner |
| 2001 | On the Relationship between Clique-Width and Treewidth. | Derek G. Corneil, Udi Rotics |
| 2001 | (k, +)-Distance-Hereditary Graphs. | Serafino Cicerone, Gianluca D'Ermiliis, Gabriele Di Stefano |
| 2001 | On Constrained Minimum Vertex Covers of Bipartite Graphs: Improved Algorithms. | Jianer Chen, Iyad A. Kanj |
| 2001 | On the Tree-Degree of Graphs. | Maw-Shang Chang, Haiko Mller |
| 2001 | Maximum Clique Transversals. | Maw-Shang Chang, Ton Kloks, Chuan-Min Lee |
| 2001 | Approximate Constrained Bipartite Edge Coloring. | Ioannis Caragiannis, Afonso Ferreira, Christos Kaklamanis, Stephane Perennes, Pino Persiano, Herv Rivano |
| 2001 | Edge-Isoperimetric Problems for Cartesian Powers of Regular Graphs. | Sergei L. Bezrukov, Robert Elssser |
| 2001 | Invited Presentation: Median Hulls as Steiner Hulls in Rectilinear and Molecular Sequence Spaces. | Hans-Jrgen Bandelt |
| 2000 | Untitled record | Emo Welzl |
| 2000 | On the Expected Runtime and the Success Probability of Evolutionary Algorithms. | Ingo Wegener |
| 2000 | Optimal Fault-Tolerant Routings for | Koichi Wada, Wei Chen |
| 2000 | A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs. | Sayaka Nagai, Shin-Ichi Nakano |
| 2000 | Coloring Mixed Hypertrees. | Daniel Krl, Jan Kratochvl, Andrzej Proskurowski, Heinz-Jrgen Voss |
| 2000 | Budget Constrained Minimum Cost Connected Medians. | Goran Konjevod, Sven Oliver Krumke, Madhav V. Marathe |
| 2000 | Recognizing Graphs without Asteroidal Triples. | Ekkehard Khler |
| 2000 | Bandwidth of Split and Circular Permutation Graphs. | Ton Kloks, Dieter Kratsch, Yvan Le Borgne, Haiko Mller |
| 2000 | The Expressive Power and Complexity of Dynamic Process Graphs. | Andreas Jakoby, Maciej Liskiewicz, Rdiger Reischuk |
| 2000 | Minimal Size of Piggybacked Information for Tracking Causality: A Graph-Based Characterization. | Jean-Michel Hlary, Giovanna Melideo |
| 2000 | Tree Spanners for Subgraphs and Related Tree Covering Problems. | Dagmar Handke, Guy Kortsarz |
| 2000 | The Tree-Width of Clique-Width Bounded Graphs Without | Frank Gurski, Egon Wanke |
| 2000 | Graph Coloring on a Coarse Grained Multiprocessor. | Assefaw Hadish Gebremedhin, Isabelle Gurin Lassous, Jens Gustedt, Jan Arne Telle |
| 2000 | Efficient Communication in Unknown Networks. | Luisa Gargano, Andrzej Pelc, Stephane Perennes, Ugo Vaccaro |
| 2000 | On the Domination Search Number. | Fedor V. Fomin, Dieter Kratsch, Haiko Mller |