| 2004 | Approximation Algorithm for Hotlink Assignment in the Greedy Model. Rachel Matichin, David Peleg |
| 2004 | Asynchronous Broadcast in Radio Networks. Bogdan S. Chlebus, Mariusz A. Rokicki |
| 2004 | Existence of Nash Equilibria in Selfish Routing Problems. Alessandro Ferrante, Mimmo Parente |
| 2004 | F-Chord: Improved Uniform Routing on Chord: (Extended Abstract). Gennaro Cordasco, Luisa Gargano, Mikael Hammar, Alberto Negro, Vittorio Scarano |
| 2004 | Fault Tolerant Forwarding and Optical Indexes: A Design Theory Approach. Arvind Gupta, Ján Manuch, Ladislav Stacho |
| 2004 | Improved Bounds for Optimal Black Hole Search with a Network Map. Stefan Dobrev, Paola Flocchini, Nicola Santoro |
| 2004 | Long-Lived Rambo: Trading Knowledge for Communication. Chryssis Georgiou, Peter M. Musial, Alexander A. Shvartsman |
| 2004 | Mobile Agents Rendezvous When Tokens Fail. Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio, Nicola Santoro, Cindy Sawchuk |
| 2004 | Morelia Test: Improving the Efficiency of the Gabriel Test and Face Routing in Ad-Hoc Networks. Paul Boone, Edgar Chávez, Lev Gleitzky, Evangelos Kranakis, Jaroslav Opatrny, Gelasio Salazar, Jorge Urrutia |
| 2004 | NP-Completeness Results for All-Shortest-Path Interval Routing. Rui Wang, Francis C. M. Lau, Yan Yan Liu |
| 2004 | No-Hole L(p, 0) Labelling of Cycles, Grids and Hypercubes. Guillaume Fertin, André Raspaud, Ondrej Sýkora |
| 2004 | On Approximability of the Independent Set Problem for Low Degree Graphs. Miroslav Chlebík, Janka Chlebíková |
| 2004 | On-Line Scheduling of Parallel Jobs. Deshi Ye, Guochuan Zhang |
| 2004 | Optimal Decision Strategies in Byzantine Environments. Michel Paquette, Andrzej Pelc |
| 2004 | Path Layout on Tree Networks: Bounds in Different Label Switching Models. Anat Bremler-Barr, Leah Epstein |
| 2004 | Perfect Token Distribution on Trees. Luciano Margara, Alessandro Pistocchi, Marco Vassura |
| 2004 | Robot Convergence via Center-of-Gravity Algorithms. Reuven Cohen, David Peleg |
| 2004 | Sharing the Cost of Multicast Transmissions in Wireless Networks. Paolo Penna, Carmine Ventre |
| 2004 | Sparse Additive Spanners for Bounded Tree-Length Graphs. Yon Dourisboure, Cyril Gavoille |
| 2004 | Structural Information and Communication Complexity, 11th International Colloquium , SIROCCO 2004, Smolenice Castle, Slovakia, June 21-23, 2004, Proceedings Rastislav Kralovic, Ondrej Sýkora |
| 2004 | Swapping a Failing Edge of a Shortest Paths Tree by Minimizing the Average Stretch Factor. Aleksej Di Salvo, Guido Proietti |
| 2004 | The Price of Anarchy in All-Optical Networks. Vittorio Bilò, Luca Moscardelli |
| 2004 | The Range Assignment Problem in Static Ad-Hoc Networks on Metric Spaces. Deshi Ye, Hu Zhang |
| 2004 | Tighter Bounds on Feedback Vertex Sets in Mesh-Based Networks. Flaminia L. Luccio, Jop F. Sibeyn |
| 2004 | Time Efficient Gossiping in Known Radio Networks. Leszek Gasieniec, Igor Potapov, Qin Xin |
| 2004 | Traffic Grooming in a Passive Star WDM Network. Eric Angel, Evripidis Bampis, Fanny Pascual |
| 2004 | Two-Hop Virtual Path Layout in Tori. Sébastien Choplin, Lata Narayanan, Jaroslav Opatrny |