| 2000 | A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs. Sayaka Nagai, Shin-Ichi Nakano |
| 2000 | Approximating Call-Scheduling Makespan in All-Optical Networks. Luca Becchetti, Miriam Di Ianni, Alberto Marchetti-Spaccamela |
| 2000 | Approximating the Treewidth of AT-Free Graphs. Vincent Bouchitté, Ioan Todinca |
| 2000 | Bandwidth of Split and Circular Permutation Graphs. Ton Kloks, Dieter Kratsch, Yvan Le Borgne, Haiko Müller |
| 2000 | Budget Constrained Minimum Cost Connected Medians. Goran Konjevod, Sven Oliver Krumke, Madhav V. Marathe |
| 2000 | Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs. Edson Cáceres, Albert Chan, Frank K. H. A. Dehne, Giuseppe Prencipe |
| 2000 | Coloring Mixed Hypertrees. Daniel Král, Jan Kratochvíl, Andrzej Proskurowski, Heinz-Jürgen Voss |
| 2000 | Computing Input Multiplicity in Anonymous Synchronous Networks with Dynamic Faults. Stefan Dobrev |
| 2000 | Diameter of the Knödel Graph. Guillaume Fertin, André Raspaud, Heiko Schröder, Ondrej Sýkora, Imrich Vrto |
| 2000 | Efficient Communication in Unknown Networks. Luisa Gargano, Andrzej Pelc, Stephane Perennes, Ugo Vaccaro |
| 2000 | Efficient Dispersion Algorithms for Geometric Intersection Graphs. Peter Damaschke |
| 2000 | Graph Coloring on a Coarse Grained Multiprocessor. Assefaw Hadish Gebremedhin, Isabelle Guérin Lassous, Jens Gustedt, Jan Arne Telle |
| 2000 | Graph-Theoretic Concepts in Computer Science, 26th International Workshop, WG 2000, Konstanz, Germany, June 15-17, 2000, Proceedings Ulrik Brandes, Dorothea Wagner |
| 2000 | Minimal Size of Piggybacked Information for Tracking Causality: A Graph-Based Characterization. Jean-Michel Hélary, Giovanna Melideo |
| 2000 | Networks with Small Stretch Number. Serafino Cicerone, Gabriele Di Stefano |
| 2000 | New Spectral Lower Bounds on the Bisection Width of Graphs. Sergei L. Bezrukov, Robert Elsässer, Burkhard Monien, Robert Preis, Jean-Pierre Tillich |
| 2000 | On the Domination Search Number. Fedor V. Fomin, Dieter Kratsch, Haiko Müller |
| 2000 | On the Expected Runtime and the Success Probability of Evolutionary Algorithms. Ingo Wegener |
| 2000 | On the Space and Access Complexity of Computation DAGs. Gianfranco Bilardi, Andrea Pietracaprina, Paolo D'Alberto |
| 2000 | Optimal Fault-Tolerant Routings for Koichi Wada, Wei Chen |
| 2000 | Optimizing Cost Flows by Modifying Arc Costs and Capacities. Ingo Demgensky, Hartmut Noltemeier, Hans-Christoph Wirth |
| 2000 | Recognizing Graphs without Asteroidal Triples. Ekkehard Köhler |
| 2000 | Split-Perfect Graphs: Characterizations and Algorithmic Use. Andreas Brandstädt, Van Bang Le |
| 2000 | The Expressive Power and Complexity of Dynamic Process Graphs. Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk |
| 2000 | The Tree-Width of Clique-Width Bounded Graphs Without Frank Gurski, Egon Wanke |
| 2000 | Traversing Directed Eulerian Mazes. Sandeep N. Bhatt, Shimon Even, David S. Greenberg, Rafi Tayar |
| 2000 | Tree Spanners for Subgraphs and Related Tree Covering Problems. Dagmar Handke, Guy Kortsarz |
| 2000 | Update Networks and Their Routing Strategies. Michael J. Dinneen, Bakhadyr Khoussainov |