| 2000 | An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree. | Q. S. Wu, Chin Lung Lu, Richard C. T. Lee |
| 2000 | A Better Lower Bound for Two-Circle Point Labeling. | Alexander Wolff, Michael Thon, Yin-Feng Xu |
| 2000 | Finding a Two-Core of a Tree in Linear Time. | Biing-Feng Wang, Jyh-Jye Lin |
| 2000 | Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width. | Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender |
| 2000 | Searching a Simple Polygon by a | Xuehou Tan |
| 2000 | Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array. | Kunihiko Sadakane |
| 2000 | Minimizing Makespan in Batch Machine Scheduling. | Chung Keung Poon, Pixing Zhang |
| 2000 | Characterization of Rooms Searchable by Two Guards. | Sang-Min Park, Kyung-Yong Chwa, Jae-Ha Lee |
| 2000 | Classification of Various Neighborhood Operations for the Nurse Scheduling Problem. | Takayuki Osogami, Hiroshi Imai |
| 2000 | On Efficient Fixed Parameter Algorithms for WEIGHTED VERTEX COVER. | Rolf Niedermeier, Peter Rossmanith |
| 2000 | Randomized Leader Election Protocols in Radio Networks with No Collision Detection. | Koji Nakano, Stephan Olariu |
| 2000 | Convex Grid Drwaings of Four-Connected Plane Graphs. | Kazuyuki Miura, Takao Nishizeki, Shin-Ichi Nakano |
| 2000 | Deterministic Broadcasting Time with Partial Knowledge of the Network. | Gianluca De Marco, Andrzej Pelc |
| 2000 | Efficient Minus and Signed Domination in Graphs. | Chin Lung Lu, Sheng-Lung Peng, Chuan Yi Tang |
| 2000 | Derandomizing Arthur-Merlin Games under Uniform Assumptions. | Chi-Jen Lu |
| 2000 | Phylogenetic | Guo-Hui Lin, Tao Jiang, Paul E. Kearney |
| 2000 | A New Competitive Analysis of Randomized Caching. | Ching Law, Charles E. Leiserson |
| 2000 | A Simple and Quick Approximation Algorithm for Traveling Salesman Problem in the Plane. | Norihiro Kubo, Shinichi Shimozono, Katsuhiro Muramoto |
| 2000 | Generalized | Petter Kristiansen, Jan Arne Telle |
| 2000 | Voronoi Diagram of a Circle Set Constructed from Voronoi Diagram of a Point Set. | Deok-Soo Kim, Donguk Kim, Kokichi Sugihara |
| 2000 | Maintenance of a Percing Set for Intervals with Applications. | Matthew J. Katz, Frank Nielsen, Michael Segal |
| 2000 | Undecidability Results for Monoids with Linear-Time Decidable Word Problems. | Masashi Katsura, Yuji Kobayashi, Friedrich Otto |
| 2000 | Unbalanced and Hierarchical Bipartite Matchings with Applications to Labeled Tree Comparison. | Ming-Yang Kao, Tak Wah Lam, Wing-Kin Sung, Hing-Fung Ting |
| 2000 | Preemptive Parallel Task Scheduling in O(n)+Poly(m) Time. | Klaus Jansen, Lorant Porkolab |
| 2000 | A Near Optimal Algorithm for Vertex Connectivity Augmentation. | Bill Jackson, Tibor Jordn |