Design and Analysis of Algorithms

1. Front Matter

   PDF

2. Detecting Approximate Periodic Patterns

   • Amihood Amir, Alberto Apostolico, Estrella Eisenberg, Gad M. Landau, Avivit Levy, Noa Lewenstein

   Pages 1-12

3. Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication

   • Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

   Pages 13-36

4. Multicast Routing for Energy Minimization Using Speed Scaling

   • Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein

   Pages 37-51

5. Reoptimization of the Minimum Total Flow-Time Scheduling Problem

   • Guy Baram, Tami Tamir

   Pages 52-66

6. Energy Efficient Caching for Phase-Change Memory

   • Neal Barcelo, Miao Zhou, Daniel Cole, Michael Nugent, Kirk Pruhs

   Pages 67-81

7. Shortest-Elapsed-Time-First on a Multiprocessor

   • Neal Barcelo, Sungjin Im, Benjamin Moseley, Kirk Pruhs

   Pages 82-92

8. Efficient Route Compression for Hybrid Route Planning

   • Gernot Veit Batz, Robert Geisberger, Dennis Luxen, Peter Sanders, Roman Zubkov

   Pages 93-107

9. Multipath Spanners via Fault-Tolerant Spanners

   • Shiri Chechik, Quentin Godfroy, David Peleg

   Pages 108-119

10. Constant Thresholds Can Make Target Set Selection Tractable

    • Morgan Chopin, André Nichterlein, Rolf Niedermeier, Mathias Weller

    Pages 120-133

11. Faster Variance Computation for Patterns with Gaps

    • Fabio Cunial

    Pages 134-147

12. Enhancing the Computation of Distributed Shortest Paths on Real Dynamic Networks

    • Gianlorenzo D’Angelo, Mattia D’Emidio, Daniele Frigioni, Daniele Romano

    Pages 148-158

13. Experimental Analysis of Rumor Spreading in Social Networks

    • Benjamin Doerr, Mahmoud Fouz, Tobias Friedrich

    Pages 159-173

14. A Randomised Approximation Algorithm for the Partial Vertex Cover Problem in Hypergraphs

    • Mourad El Ouali, Helena Fohlin, Anand Srivastav

    Pages 174-187

15. Simulation-Based Analysis of Topology Control Algorithms for Wireless Ad Hoc Networks

    • Fabian Fuchs, Markus Völker, Dorothea Wagner

    Pages 188-202

16. Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability

    • Michael T. Goodrich, Daniel S. Hirschberg, Michael Mitzenmacher, Justin Thaler

    Pages 203-218

17. An Efficient Generator for Clustered Dynamic Random Networks

    • Robert Görke, Roland Kluge, Andrea Schumm, Christian Staudt, Dorothea Wagner

    Pages 219-233

18. Slow Down and Sleep for Profit in Online Deadline Scheduling

    • Peter Kling, Andreas Cord-Landwehr, Frederik Mallmann-Trenn

    Pages 234-247

19. FIFO Queueing Policies for Packets with Heterogeneous Processing

    • Kirill Kogan, Alejandro López-Ortiz, Sergey I. Nikolenko, Alexander V. Sirotkin, Denis Tugaryov

    Pages 248-260

20. Back Matter

    PDF

This book constitutes the refereed proceedings of the First Mediterranean Conference on Algorithms, MedAlg 2012, held in Kibbutz Ein Gedi, Israel, in December 2012.
The 18 papers presented were carefully reviewed and selected from 44 submissions. The conference papers focus on the design, engineering, theoretical and experimental performance analysis of algorithms for problems arising in different areas of computation. Topics covered include: communications networks, combinatorial optimization and approximation, parallel and distributed computing, computer systems and architecture, economics, game theory, social networks and the World Wide Web.

• dynamic networks
• graphs
• periodic patterns
• routing
• scheduling
• algorithm analysis and problem complexity
• data structures

• School of Electrical Engineering, Tel-Aviv University, Tel Aviv, Israel

  Guy Even

• School of Electrical Engineering, Tel-Aviv University, Tel-Aviv, Israel

  Dror Rawitz

Policies and ethics