17. SPAA 2005: Las Vegas, Nevada, USA

Phillip B. Gibbons, Paul G. Spirakis (Eds.): SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallel Algorithms, July 18-20, 2005, Las Vegas, Nevada, USA. ACM 2005, ISBN 1-58113-986-1 BibTeX

Queuing and scheduling

Nir Andelman:
Randomized queue management for DiffServ. 1-10
Electronic Edition (ACM DL) BibTeX
Hagit Attiya, David Hay:
Randomization does not reduce the average delay in parallel packet switches. 11-20
Electronic Edition (ACM DL) BibTeX
David Chase, Yossi Lev:
Dynamic circular work-stealing deque. 21-28
Electronic Edition (ACM DL) BibTeX
Ajay Gulati, Peter J. Varman:
Lexicographic QoS scheduling for parallel I/O. 29-38
Electronic Edition (ACM DL) BibTeX

Joint session

Thomas Moscibroda, Roger Wattenhofer:
Coloring unstructured radio networks. 39-48
Electronic Edition (ACM DL) BibTeX
Ittai Abraham, Dahlia Malkhi:
Name independent routing for growth bounded networks. 49-55
Electronic Edition (ACM DL) BibTeX

Scheduling

Amotz Bar-Noy, Richard E. Ladner, Tami Tamir, Tammy VanDeGrift:
Windows scheduling of arbitrary length jobs on parallel machines. 56-65
Electronic Edition (ACM DL) BibTeX
Grzegorz Malewicz:
Parallel scheduling of complex dags under uncertainty. 66-75
Electronic Edition (ACM DL) BibTeX
Ami Litman, Shiri Moran-Schein:
On distributed smooth scheduling. 76-85
Electronic Edition (ACM DL) BibTeX
Klaus Jansen, Hu Zhang:
Scheduling malleable tasks with precedence constraints. 86-95
Electronic Edition (ACM DL) BibTeX

Sensor networks and ad hoc networks

Ioannis Chatzigiannakis, Athanasios Kinalis, Sotiris E. Nikoletseas:
An adaptive power conservation scheme for heterogeneous wireless sensor networks with node redeployment. 96-105
Electronic Edition (ACM DL) BibTeX
Devdatt P. Dubhashi, C. Johansson, Olle Häggström, Alessandro Panconesi, Mauro Sozio:
Irrigating ad hoc networks in constant time. 106-115
Electronic Edition (ACM DL) BibTeX
Kishore Kothapalli, Christian Scheideler, Melih Onus, Andréa W. Richa:
Constant density spanners for wireless ad-hoc networks. 116-125
Electronic Edition (ACM DL) BibTeX

Peer-to-peer networks

James Aspnes, Udi Wieder:
The expansion and mixing time of skip graphs with applications. 126-134
Electronic Edition (ACM DL) BibTeX
Krishnaram Kenthapadi, Gurmeet Singh Manku:
Decentralized algorithms using both local and random probes for P2P load balancing. 135-144
Electronic Edition (ACM DL) BibTeX
Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu, Yitong Yin:
Fast construction of overlay networks. 145-154
Electronic Edition (ACM DL) BibTeX
Peter Mahlmann, Christian Schindelhauer:
Peer-to-peer networks based on random transformations of connected regular undirected graphs. 155-164
Electronic Edition (ACM DL) BibTeX

Parallel and quantum algorithms

Piotr Sankowski:
Processor efficient parallel matching. 165-170
Electronic Edition (ACM DL) BibTeX
Ryan Williams:
Parallelizing time with polynomial circuits. 171-175
Electronic Edition (ACM DL) BibTeX
Bruce M. Maggs, Gary L. Miller, Ojas Parekh, R. Ravi, Shan Leung Maverick Woo:
Finding effective support-tree preconditioners. 176-185
Electronic Edition (ACM DL) BibTeX
Lov K. Grover, Jaikumar Radhakrishnan:
Is partial quantum search of a database any easier? 186-194
Electronic Edition (ACM DL) BibTeX

Game theory

Guido Proietti, Peter Widmayer:
A truthful mechanism for the non-utilitarian minimum radius spanning tree problem. 195-202
Electronic Edition (ACM DL) BibTeX
Martin Gairing, Burkhard Monien, Karsten Tiemann:
Selfish routing with incomplete information. 203-212
Electronic Edition (ACM DL) BibTeX

Brief announcements

Bradley C. Kuszmaul:
A segmented parallel-prefix VLSI circuit with small delays for small segments. 213
Electronic Edition (ACM DL) BibTeX
Ioannis Chatzigiannakis, Sotiris E. Nikoletseas:
A forward planning situated protocol for data propagation in wireless sensor networks based on swarm intelligence techniques. 214
Electronic Edition (ACM DL) BibTeX
Shlomi Dolev, Seth Gilbert, Elad Schiller, Alexander A. Shvartsman, Jennifer L. Welch:
Autonomous virtual mobile nodes. 215
Electronic Edition (ACM DL) BibTeX
Kofi A. Laing, Rajmohan Rajaraman:
A space lower bound for name-independent compact routing in trees. 216
Electronic Edition (ACM DL) BibTeX
Rahul Shah, Peter J. Varman, Jeffrey Scott Vitter:
On competitive online read-many parallel disks scheduling. 217
Electronic Edition (ACM DL) BibTeX

Algorithms and data structures

Christian Schindelhauer, Gunnar Schomaker:
Weighted distributed hash tables. 218-227
Electronic Edition (ACM DL) BibTeX
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Bradley C. Kuszmaul:
Concurrent cache-oblivious b-trees. 228-237
Electronic Edition (ACM DL) BibTeX
Noga Alon, Yossi Azar, Shai Gutner:
Admission control to minimize rejections and online set cover with repetitions. 238-244
Electronic Edition (ACM DL) BibTeX
Chaiyasit Manovit, Sudheendra Hangal:
Efficient algorithms for verifying memory consistency. 245-252
Electronic Edition (ACM DL) BibTeX

Joint session

Mark Moir, Daniel Nussbaum, Ori Shalev, Nir Shavit:
Using elimination to implement scalable and lock-free FIFO queues. 253-262
Electronic Edition (ACM DL) BibTeX
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-Shamir, Mark R. Tuttle:
Collaborate with strangers to find own preferences. 263-269
Electronic Edition (ACM DL) BibTeX

Miscellaneous

Marcin Bienkowski:
Dynamic page migration with stochastic requests. 270-278
Electronic Edition (ACM DL) BibTeX
Samir Khuller, Yoo Ah Kim, Yung-Chun (Justin) Wan:
Broadcasting on networks of workstations. 279-288
Electronic Edition (ACM DL) BibTeX
Randeep Bhatia, Nicole Immorlica, Tracy Kimbrel, Vahab S. Mirrokni, Seffi Naor, Baruch Schieber:
Traffic engineering of management flows by link augmentations on confluent trees. 289-298
Electronic Edition (ACM DL) BibTeX
Eric Anderson, Dirk Beyer, Kamalika Chaudhuri, Terence Kelly, Norman Salazar, Cipriano A. Santos, Ram Swaminathan, Robert Endre Tarjan, Janet L. Wiener, Yunhong Zhou:
Value-maximizing deadline scheduling and its application to animation rendering. 299-308
Electronic Edition (ACM DL) BibTeX

Radio networks

Robert Elsässer, Leszek Gasieniec:
Radio communication in random graphs: extended abstract. 309-315
Electronic Edition (ACM DL) BibTeX
Costas Busch, Malik Magdon-Ismail, Jing Xi:
Oblivious routing on geometric networks. 316-324
Electronic Edition (ACM DL) BibTeX
Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, Charles E. Leiserson:
Adversarial contention resolution for simple channels. 325-332
Electronic Edition (ACM DL) BibTeX