| 2004 | A Fast Distributed Algorithm for Approximating the Maximum Matching. Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymanska |
| 2004 | A Parameterized Algorithm for Upward Planarity Testing. Hubert Y. Chan |
| 2004 | A Straight Skeleton Approximating the Medial Axis. Mirela Tanase, Remco C. Veltkamp |
| 2004 | A Survey of FPT Algorithm Design Techniques with an Emphasis on Recent Advances and Connections to Practical Computing. Michael R. Fellows |
| 2004 | Algorithmic Aspects of Web Search Engines. Monika Henzinger |
| 2004 | Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings Susanne Albers, Tomasz Radzik |
| 2004 | Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems. Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich |
| 2004 | An Algorithm for Computing DNA Walks. Ankur Bhargava, S. Rao Kosaraju |
| 2004 | An Approximation Algorithm for Maximum Triangle Packing. Refael Hassin, Shlomi Rubinstein |
| 2004 | An Experimental Study of Random Knapsack Problems. René Beier, Berthold Vöcking |
| 2004 | An Improved Algorithm for CIOQ Switches. Yossi Azar, Yossi Richter |
| 2004 | An Inductive Construction for Plane Laman Graphs via Vertex Splitting. Zsolt Fekete, Tibor Jordán, Walter Whiteley |
| 2004 | Approximate Parameterized Matching. Carmit Hazay, Moshe Lewenstein, Dina Sokol |
| 2004 | Approximate Unions of Lines and Minkowski Sums. Marc J. van Kreveld, A. Frank van der Stappen |
| 2004 | Approximation Algorithms for Quickest Spanning Tree Problems. Refael Hassin, Asaf Levin |
| 2004 | Approximation Hardness of Dominating Set Problems. Miroslav Chlebík, Janka Chlebíková |
| 2004 | Approximation of Rectangle Stabbing and Interval Stabbing Problems. Sofia Kovaleva, Frits C. R. Spieksma |
| 2004 | Beyond Optimal Play in Two-Person-Zerosum Games. Ulf Lorenz |
| 2004 | Classroom Examples of Robustness Problems in Geometric Computations. Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee-Keng Yap |
| 2004 | Code Flexibility and Program Efficiency by Genericity: Improving Cgal's Arrangements. Efi Fogel, Ron Wein, Dan Halperin |
| 2004 | Comparing Real Algebraic Numbers of Small Degree. Ioannis Z. Emiris, Elias P. Tsigaridas |
| 2004 | Competitive Online Approximation of the Optimal Search Ratio. Rudolf Fleischer, Thomas Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen |
| 2004 | Construction of Minimum-Weight Spanners. Mikkel Sigurd, Martin Zachariasen |
| 2004 | Contraction and Treewidth Lower Bounds. Hans L. Bodlaender, Arie M. C. A. Koster, Thomas Wolle |
| 2004 | Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems. Reuven Cohen, David Peleg |
| 2004 | Data Migration on Parallel Disks. Leana Golubchik, Samir Khuller, Yoo Ah Kim, Svetlana Shargorodskaya, Yung-Chun (Justin) Wan |
| 2004 | Direct Routing: Algorithms and Complexity. Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, Paul G. Spirakis |
| 2004 | Dynamic Shannon Coding. Travis Gagie |
| 2004 | Efficient IP Table Lookup via Adaptive Stratified Trees with Selective Reconstructions. Marco Pellegrini, Giordano Fusco |
| 2004 | Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects. Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Hai Yu |
| 2004 | Equivalence of Search Capability Among Mobile Guards with Various Visibilities. Jae-Ha Lee, Sang-Min Park, Kyung-Yong Chwa |
| 2004 | Extreme Points Under Random Noise. Valentina Damerow, Christian Sohler |
| 2004 | Fast 3-Coloring Triangle-Free Planar Graphs. Lukasz Kowalik |
| 2004 | Fast Multipoint Evaluation of Bivariate Polynomials. Michael Nüsken, Martin Ziegler |
| 2004 | Fast Sparse Matrix Multiplication. Raphael Yuster, Uri Zwick |
| 2004 | Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems. Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, Sue Whitesides |
| 2004 | Finding Dominators in Practice. Loukas Georgiadis, Renato Fonseca F. Werneck, Robert Endre Tarjan, Spyridon Triantafyllis, David I. August |
| 2004 | Fisher Equilibrium Price with a Class of Concave Utility Functions. Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao |
| 2004 | Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings. Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos |
| 2004 | Flows on Few Paths: Algorithms and Lower Bounds. Maren Martens, Martin Skutella |
| 2004 | Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries. Naveen Garg, Rohit Khandekar |
| 2004 | Graph Decomposition Lemmas and Their Role in Metric Embedding Methods. Yair Bartal |
| 2004 | Hardness and Approximation Results for Packing Steiner Trees. Joseph Cheriyan, Mohammad R. Salavatipour |
| 2004 | Improved Online Algorithms for Buffer Management in QoS Switches. Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý |
| 2004 | Incremental Algorithms for Facility Location and k-Median. Dimitris Fotakis |
| 2004 | Labeling Smart Dust. Vikas Bansal, Friedhelm Meyer auf der Heide, Christian Sohler |
| 2004 | Load Balancing in Hypercubic Distributed Hash Tables with Heterogeneous Processors. Junning Liu, Micah Adler |
| 2004 | Load Balancing of Indivisible Unit Size Tokens in Dynamic and Heterogeneous Networks. Robert Elsässer, Burkhard Monien, Stefan Schamberger |
| 2004 | Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families. Douglas E. Carroll, Ashish Goel |
| 2004 | Maximizing Throughput in Multi-queue Switches. Yossi Azar, Arik Litichevskey |
| 2004 | Maximum Matchings in Planar Graphs via Gaussian Elimination. Marcin Mucha, Piotr Sankowski |
| 2004 | Modeling Locality: A Probabilistic Analysis of LRU and FWF. Luca Becchetti |
| 2004 | Multi-word Atomic Read/Write Registers on Multiprocessor Systems. Andreas Larsson, Anders Gidenstam, Phuong Hoai Ha, Marina Papatriantafilou, Philippas Tsigas |
| 2004 | Negotiation-Range Mechanisms: Coalition-Resistant Markets. Rica Gonen |
| 2004 | Non-additive Shortest Paths. George Tsaggouris, Christos D. Zaroliagis |
| 2004 | On Adaptive Integer Sorting. Anna Pagh, Rasmus Pagh, Mikkel Thorup |
| 2004 | On Dynamic Shortest Paths Problems. Liam Roditty, Uri Zwick |
| 2004 | On Rectangular Cartograms. Marc J. van Kreveld, Bettina Speckmann |
| 2004 | On Variable-Sized Multidimensional Packing. Leah Epstein, Rob van Stee |
| 2004 | On the Evolution of Selfish Routing. Simon Fischer, Berthold Vöcking |
| 2004 | On the Stability of Multiple Partner Stable Marriages with Ties. Varun S. Malhotra |
| 2004 | Optimal External Memory Planar Point Enclosure. Lars Arge, Vasilis Samoladas, Ke Yi |
| 2004 | Path Decomposition Under a New Cost Measure with Applications to Optical Network Design. Elliot Anshelevich, Lisa Zhang |
| 2004 | Radio Network Clustering from Scratch. Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer |
| 2004 | Seeking a Vertex of the Planar Matching Polytope in NC. Raghav Kulkarni, Meena Mahajan |
| 2004 | Solving Geometric Covering Problems by Data Reduction. Steffen Mecke, Dorothea Wagner |
| 2004 | Stable Minimum Storage Merging by Symmetric Comparisons. Pok-Son Kim, Arne Kutzner |
| 2004 | Super Scalar Sample Sort. Peter Sanders, Sebastian Winkel |
| 2004 | Swap and Mismatch Edit Distance. Amihood Amir, Estrella Eisenberg, Ely Porat |
| 2004 | The Average Case Analysis of Partition Sorts. Richard Cole, David C. Kandathil |
| 2004 | Tiling a Polygon with Two Kinds of Rectangles. Eric Rémila |
| 2004 | Time Dependent Multi Scheduling of Multicast. Rami Cohen, Dror Rawitz, Danny Raz |
| 2004 | Uniform Algorithms for Deterministic Construction of Efficient Dictionaries. Milan Ruzic |