9. SWAT 2004: Humlebæk, Denmark

Invited Contributions

• Charles E. Leiserson:
  Design and Analysis of Dynamic Multithreaded Algorithms. 1-2
  
• Gerth Stølting Brodal:
  Cache-Oblivious Algorithms and Data Structures. 3-13
  

Refereed Contributions

• Kirk Pruhs, Patchrawat Uthaisombut, Gerhard J. Woeginger:
  Getting the Best Response for Your Erg. 14-25
  
• Nir Andelman, Yishay Mansour:
  Auctions with Budget Constraints. 26-38
  
• Piotr Berman, Bhaskar DasGupta, Ming-Yang Kao:
  Tight Approximability Results for Test Set Problems in Bioinformatics. 39-50
  
• Refael Hassin, Danny Segev:
  Robust Subgraphs for Trees and Paths. 51-63
  
• Feodor F. Dragan, Chenyu Yan, Irina Lomonosov:
  Collective Tree Spanners of Graphs. 64-76
  
• Wolfgang W. Bein, Leah Epstein, Lawrence L. Larmore, John Noga:
  Optimally Competitive List Batching. 77-89
  
• Joan Boyar, Paul Medvedev:
  The Relative Worst Order Ratio Applied to Seat Reservation. 90-101
  
• Rudolf Fleischer, Mordecai J. Golin, Yan Zhang:
  Online Maintenance of k-Medians and k-Covers on a Line. 102-113
  
• Vladlen Koltun, Carola Wenk:
  Matching Polyhedral Terrains Using Overlays of Envelopes. 114-126
  
• Pankaj K. Agarwal, Nabil H. Mustafa:
  Independent Set of Intersection Graphs of Convex Objects in 2D. 127-137
  
• Mark de Berg, Sergio Cabello, Panos Giannopoulos, Christian Knauer, René van Oostrum, Remco C. Veltkamp:
  Maximizing the Area of Overlap of Two Unions of Disks Under Rigid Motion. 138-149
  
• Mee Yee Chan, Danny Z. Chen, Francis Y. L. Chin, Cao An Wang:
  Construction of the Nearest Neighbor Embracing Graph of a Point Set. 150-160
  
• Norbert Zeh:
  Connectivity of Graphs Under Edge Flips. 161-173
  
• Miroslav Chlebík, Janka Chlebíková:
  Improvement of Nemhauser-Trotter Theorem and Its Applications in Parametrized Complexity. 174-186
  
• Michel Habib, Fabien de Montgolfier, Christophe Paul:
  A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension. 187-198
  
• Michael Gatto, Björn Glaus, Riko Jacob, Leon Peeters, Peter Widmayer:
  Railway Delay Management: Exploring Its Algorithmic Complexity. 199-211
  
• Amr Elmasry:
  Layered Heaps. 212-222
  
• Ran Mendelson, Robert Endre Tarjan, Mikkel Thorup, Uri Zwick:
  Melding Priority Queues. 223-235
  
• Zdenek Dvorak, Jan Kára, Daniel Král, Ondrej Pangrác:
  An Algorithm for Cyclic Edge Connectivity of Cubic Graphs. 236-247
  
• Anders Dessmark, Andrzej Lingas, Eva-Marta Lundell:
  Subexponential-Time Framework for Optimal Embeddings of Graphs in Integer Lattices. 248-259
  
• Kazuhisa Makino, Takeaki Uno:
  New Algorithms for Enumerating All Maximal Cliques. 260-272
  
• Adi Avidor, Michael Langberg:
  The Multi-multiway Cut Problem. 273-284
  
• Andrew Lim, Zhou Xu:
  The Bottleneck Problem with Minimum Quantity Commitments. 285-297
  
• Yossi Azar, Shai Taub:
  All-Norm Approximation for Scheduling on Identical Machines. 298-310
  
• Klaus Jansen:
  Approximation Algorithms for the General Max-min Resource Sharing Problem: Faster and Simpler. 311-322
  
• Andrew Lim, Brian Rodrigues, Zhou Xu:
  Approximation Schemes for the Crane Scheduling Problem. 323-335
  
• Raja Jothi, Balaji Raghavachari:
  Improved Approximation Algorithms for the Single-Sink Buy-at-Bulk Network Design Problems. 336-348
  
• Kazuo Iwama, Shuichi Miyazaki, Kazuya Okamoto:
  A (2-c(log N/N))-Approximation Algorithm for the Stable Marriage Problem. 349-361
  
• Klaus Jansen, Guochuan Zhang:
  Maximizing the Number of Packed Rectangles. 362-371
  
• Giovanni Manzini:
  Two Space Saving Tricks for Linear Time LCP Array Computation. 372-383
  
• Mikkel Thorup:
  Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles. 384-396
  
• Leszek Gasieniec, Tomasz Radzik, Qin Xin:
  Faster Deterministic Gossiping in Directed Ad Hoc Radio Networks. 397-407
  
• Leah Epstein, Rob van Stee:
  Online Scheduling of Splittable Tasks in Peer-to-Peer Networks. 408-419
  
• Patchrawat Uthaisombut:
  The Optimal Online Algorithms for Minimizing Maximum Lateness. 420-430
  
• Paz Carmi, Matthew J. Katz:
  Power Assignment in Radio Networks with Two Power Levels. 431-441
  
• Michael Hoffmann, Bettina Speckmann, Csaba D. Tóth:
  Pointed Binary Encompassing Trees. 442-454
  
• Tetsuo Asano, Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama:
  On Geometric Structure of Global Roundings for Graphs and Range Spaces. 455-467
  
• Jop F. Sibeyn:
  External Connected Components. 468-479
  
• Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, Norbert Zeh:
  Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths. 480-492
  
• Lars Arge, Laura Toma:
  Simplified External Memory Algorithms for Planar DAGs. 493-503
  

Last update Mon Feb 13 04:41:52 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page