| 2004 | The Maximum Agreement of Two Nested Phylogenetic Networks. | Jesper Jansson, Wing-Kin Sung |
| 2004 | Local Gapped Subforest Alignment and Its Application in Finding RNA Structural Motifs. | Jesper Jansson, Ngo Trung Hieu, Wing-Kin Sung |
| 2004 | Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting. | Joseph F. JJ, Christian Worm Mortensen, Qingmin Shi |
| 2004 | Approximated Two Choices in Randomized Load Balancing. | Kazuo Iwama, Akinori Kawachi |
| 2004 | Paired Pointset Traversal. | Peter Hui, Marcus Schaefer |
| 2004 | Adaptive Spatial Partitioning for Multidimensional Data Streams. | John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba D. Tth |
| 2004 | Counting Spanning Trees and Other Structures in Non-constant-jump Circulant Graphs. | Mordecai J. Golin, Yiu-Cho Leung, Yajun Wang |
| 2004 | Minimum Common String Partition Problem: Hardness and Approximations. | Avraham Goldstein, Petr Kolman, Jie Zheng |
| 2004 | On the Complexity of Network Synchronization. | Darin Goldstein, Kojiro Kobayashi |
| 2004 | On the Hardness and Easiness of Random 4-SAT Formulas. | Andreas Goerdt, Andr Lanka |
| 2004 | GCD of Random Linear Forms. | Joachim von zur Gathen, Igor E. Shparlinski |
| 2004 | Fast Algorithms for Comparison of Similar Unordered Trees. | Daiji Fukagawa, Tatsuya Akutsu |
| 2004 | Three-Round Adaptive Diagnosis in Binary n-Cubes. | Satoshi Fujita, Toru Araki |
| 2004 | Diagnosis in the Presence of Intermittent Faults. | Bin Fu, Richard Beigel |
| 2004 | Randomized Insertion and Deletion in Point Quad Trees. | Amalia Duch |
| 2004 | On Compact and Efficient Routing in Certain Graph Classes. | Feodor F. Dragan, Irina Lomonosov |
| 2004 | Error Compensation in Leaf Root Problems. | Michael Dom, Jiong Guo, Falk Hffner, Rolf Niedermeier |
| 2004 | Puzzles, Art, and Magic with Algorithms. | Erik D. Demaine |
| 2004 | Composability of Infinite-State Activity Automata. | Zhe Dang, Oscar H. Ibarra, Jianwen Su |
| 2004 | On p-Norm Based Locality Measures of Space-Filling Curves. | H. K. Dai, Hung-Chi Su |
| 2004 | Cutting Out Polygons with Lines and Rays. | Ovidiu Daescu, Jun Luo |
| 2004 | Guarding Art Galleries by Guarding Witnesses. | Kyung-Yong Chwa, Byung-Cheol Jo, Christian Knauer, Esther Moet, Ren van Oostrum, Chan-Su Shin |
| 2004 | An Efficient Algorithm for Finding Maximum Cycle Packings in Reducible Flow Graphs. | Xujin Chen, Wenan Zang |
| 2004 | Efficient Job Scheduling Algorithms with Multi-type Contentions. | Zhenming Chen, Vikas Singh, Jinhui Xu |
| 2004 | Generalized Geometric Approaches for Leaf Sequencing Problems in Radiation Therapy. | Danny Z. Chen, Xiaobo Sharon Hu, Shuang Luan, Shahid A. Naqvi, Chao Wang, Cedric X. Yu |