Algorithm theory -- SWAT 2004. 9th Scandinavian workshop on algorithm theory, Humlebæk, Denmark, July 8--10, 2004. Proceedings. (Q1763062)

The articles of this volume will be reviewed individually. The preceding workshop has been reviewed (see Zbl 0992.00054). Indexed articles: \textit{Leiserson, Charles E.}, Design and analysis of dynamic multithreaded algorithms, 1-2 [Zbl 1095.68745] \textit{Brodal, Gerth Stølting}, Cache-oblivious algorithms and data structures, 3-13 [Zbl 1095.68742] \textit{Pruhs, Kirk; Uthaisombut, Patchrawat; Woeginger, Gerhard}, Getting the best response for your erg, 14-25 [Zbl 1095.68553] \textit{Andelman, Nir; Mansour, Yishay}, Auctions with budget constraints, 26-38 [Zbl 1095.91504] \textit{Berman, Piotr; DasGupta, Bhaskar; Kao, Ming-Yang}, Tight approximability results for test set problems in bioinformatics, 39-50 [Zbl 1095.68596] \textit{Hassin, Refael; Segev, Danny}, Robust subgraphs for trees and paths, 51-63 [Zbl 1095.68623] \textit{Dragan, Feodor F.; Yan, Chenyu; Lomonosov, Irina}, Collective tree spanners of graphs, 64-76 [Zbl 1095.05500] \textit{Bein, Wolfgang W.; Epstein, Leah; Larmore, Lawrence L.; Noga, John}, Optimally competitive list batching, 77-89 [Zbl 1095.90546] \textit{Boyar, Joan; Medvedev, Paul}, The relative worst order ratio applied to seat reservation, 90-101 [Zbl 1095.68753] \textit{Fleischer, Rudolf; Golin, Mordecai J.; Zhang, Yan}, Online maintenance of \(k\)-medians and \(k\)-covers on a line, 102-113 [Zbl 1095.68754] \textit{Koltun, Vladlen; Wenk, Carola}, Matching polyhedral terrains using overlays of envelopes (extended abstract), 114-126 [Zbl 1095.68717] \textit{Agarwal, Pankaj K.; Mustafa, Nabil H.}, Independent set of intersection graphs of convex objects in 2D, 127-137 [Zbl 1095.68712] \textit{de Berg, Mark; Cabello, Sergio; Giannopoulos, Panos; Knauer, Christian; van Oostrum, René; Veltkamp, Remco C.}, Maximizing the area of overlap of two unions of disks under rigid motion, 138-149 [Zbl 1095.68720] \textit{Chan, M. Y.; Chen, Danny; Chin, Francis Y. L.; Wang, Cao An}, Construction of the nearest neighbor embracing graph of a point set, 150-160 [Zbl 1095.68714] \textit{Zeh, Norbert}, Connectivity of graphs under edge flips, 161-173 [Zbl 1095.68629] \textit{Chlebík, Miroslav; Chlebíková, Janka}, Improvement of Nemhauser-Trotter theorem and its applications in parametrized complexity, 174-186 [Zbl 1095.68077] \textit{Habib, Michel; de Montgolfier, Fabien; Paul, Christophe}, A simple linear-time modular decomposition algorithm for graphs, using order extension, 187-198 [Zbl 1095.68622] \textit{Gatto, Michael; Glaus, Björn; Jacob, Riko; Peeters, Leon; Widmayer, Peter}, Railway delay management: Exploring its algorithmic complexity, 199-211 [Zbl 1095.68595] \textit{Elmasry, Amr}, Layered heaps, 212-222 [Zbl 1095.68574] \textit{Mendelson, Ran; Tarjan, Robert E.; Thorup, Mikkel; Zwick, Uri}, Melding priority queues, 223-235 [Zbl 1095.68577] \textit{Dvořák, Zdeněk; Kára, Jan; Král', Daniel; Pangrác, Ondřej}, An algorithm for cyclic edge connectivity of cubic graphs (extended abstract), 236-247 [Zbl 1095.68619] \textit{Dessmark, Anders; Lingas, Andrzej; Lundell, Eva-Marta}, Subexponential-time framework for optimal embeddings of graphs in integer lattices, 248-259 [Zbl 1095.68618] \textit{Makino, Kazuhisa; Uno, Takeaki}, New algorithms for enumerating all maximal cliques, 260-272 [Zbl 1095.68626] \textit{Avidor, Adi; Langberg, Michael}, The multi-multiway cut problem, 273-284 [Zbl 1095.68617] \textit{Lim, Andrew; Xu, Zhou}, The bottleneck problem with minimum quantity commitments, 285-297 [Zbl 1095.90603] \textit{Azar, Yossi; Taub, Shai}, All-norm approximation for scheduling on identical machines, 298-310 [Zbl 1095.90542] \textit{Jansen, Klaus}, Approximation algorithms for the general max-min resource sharing problem: Faster and simpler, 311-322 [Zbl 1095.90604] \textit{Lim, Andrew; Rodrigues, Brian; Xu, Zhou}, Approximation schemes for the crane scheduling problem, 323-335 [Zbl 1095.90551] \textit{Jothi, Raja; Raghavachari, Balaji}, Improved approximation algorithms for the single-sink buy-at-bulk network design problems, 336-348 [Zbl 1095.90517] \textit{Iwama, Kazuo; Miyazaki, Shuichi; Okamoto, Kazuya}, A \(\left( 2 - c \frac{\log N}{N} \right)\)-approximation algorithm for the stable marriage problem, 349-361 [Zbl 1095.68749] \textit{Jansen, Klaus; Zhang, Guochuan}, Maximizing the number of packed rectangles, 362-371 [Zbl 1095.68750] \textit{Manzini, Giovanni}, Two space saving tricks for linear time LCP array computation, 372-383 [Zbl 1095.68755] \textit{Thorup, Mikkel}, Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles, 384-396 [Zbl 1095.68628] \textit{Gąsieniec, Leszek; Radzik, Tomasz; Xin, Qin}, Faster deterministic gossiping in directed ad hoc radio networks, 397-407 [Zbl 1095.68511] \textit{Epstein, Leah; van Stee, Rob}, Online scheduling of splittable tasks in peer-to-peer networks, 408-419 [Zbl 1095.68547] \textit{Uthaisombut, Patchrawat}, The optimal online algorithms for minimizing maximum lateness, 420-430 [Zbl 1095.90558] \textit{Carmi, Paz; Katz, Matthew J.}, Power assignment in radio networks with two power levels, 431-441 [Zbl 1095.68505] \textit{Hoffmann, Michael; Speckmann, Bettina; Tóth, Csaba D.}, Pointed binary encompassing trees, 442-454 [Zbl 1095.68716] \textit{Asano, Tetsuo; Katoh, Naoki; Tamaki, Hisao; Tokuyama, Takeshi}, On geometric structure of global roundings for graphs and range spaces, 455-467 [Zbl 1095.68713] \textit{Sibeyn, Jop F.}, External connected components, 468-479 [Zbl 1095.68627] \textit{Brodal, Gerth Stølting; Fagerberg, Rolf; Meyer, Ulrich; Zeh, Norbert}, Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths, 480-492 [Zbl 1095.68572] \textit{Arge, Lars; Toma, Laura}, Simplified external memory algorithms for planar DAGs, 493-503 [Zbl 1095.68616]