| 2004 | Oriented Paths in Mixed Graphs. | Egon Wanke, Rolf Ktter |
| 2004 | Randomized Algorithms for Motif Detection. | Lusheng Wang, Liang Dong, Hui Fan |
| 2004 | Efficient Algorithms for the Longest Path Problem. | Ryuhei Uehara, Yushi Uno |
| 2004 | Canonical Data Structure for Interval Probe Graphs. | Ryuhei Uehara |
| 2004 | Approximation Algorithms for the Consecutive Ones Submatrix Problem on Sparse Matrices. | Jinsong Tan, Louxin Zhang |
| 2004 | The Two-Guard Problem Revisited and Its Generalization. | Xuehou Tan |
| 2004 | Techniques for Indexing and Querying Temporal Observations for a Collection of Objects. | Qingmin Shi, Joseph F. JJ |
| 2004 | Spanners, Weak Spanners, and Power Spanners for Wireless Networks. | Christian Schindelhauer, Klaus Volbert, Martin Ziegler |
| 2004 | Dynamic Tree Cross Products. | Marcus Raitner |
| 2004 | Efficient Algorithms for the Hotlink Assignment Problem: The Worst Case Search. | Artur Alves Pessoa, Eduardo Sany Laber, Crston P. de Souza |
| 2004 | Planning the Transportation of Multiple Commodities in Bidirectional Pipeline Networks. | Artur Alves Pessoa |
| 2004 | An O(n log n)-Time Algorithm for the Maximum Constrained Agreement Subtree Problem for Binary Trees. | Zeshan Peng, Hing-Fung Ting |
| 2004 | Many-to-many Disjoint Path Covers in a Graph with Faulty Elements. | Jung-Heum Park, Hee-Chul Kim, Hyeong-Seok Lim |
| 2004 | Exact Computation of Polynomial Zeros Expressible by Square Roots. | Timo von Oertzen |
| 2004 | Boundary-Optimal Triangulation Flooding. | Richard J. Nowakowski, Norbert Zeh |
| 2004 | Approximating the Minmax Subtree Cover Problem in a Cactus. | Hiroshi Nagamochi, Taizo Kawada |
| 2004 | The ABCs of AVDs: Geometric Retrieval Made Simple. | David M. Mount |
| 2004 | Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation. | Jrme Monnot, Vangelis Th. Paschos, Dominique de Werra, Marc Demange, Bruno Escoffier |
| 2004 | Inner Rectangular Drawings of Plane Graphs. | Kazuyuki Miura, Hiroki Haga, Takao Nishizeki |
| 2004 | Advantages of Backward Searching - Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays. | Veli Mkinen, Gonzalo Navarro, Kunihiko Sadakane |
| 2004 | Distributions of Points and Large Quadrangles. | Hanno Lefmann |
| 2004 | Polynomial Deterministic Rendezvous in Arbitrary Graphs. | Dariusz R. Kowalski, Andrzej Pelc |
| 2004 | Optimal Buffer Management via Resource Augmentation. | Jae-Hoon Kim |
| 2004 | New Bounds on Map Labeling with Circular Labels. | Minghui Jiang, Sergey Bereg, Zhongping Qin, Binhai Zhu |
| 2004 | Sequences of Radius k: How to Fetch Many Huge Objects into Small Memory for Pairwise Computations. | Jerzy W. Jaromczyk, Zbigniew Lonc |