Detecting Approximate Periodic Patterns / Amihood Amir, Alberto Apostolico, Estrella Eisenberg -- Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication / Grey Ballard, James Demmel, Olga Holtz -- Multicast Routing for Energy Minimization Using Speed Scaling / Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy -- Reoptimization of the Minimum Total Flow-Time Scheduling Problem / Guy Baram, Tami Tamir -- Energy Efficient Caching for Phase-Change Memory / Neal Barcelo, Miao Zhou, Daniel Cole, Michael Nugent -- Shortest-Elapsed-Time-First on a Multiprocessor / Neal Barcelo, Sungjin Im, Benjamin Moseley, Kirk Pruhs -- Efficient Route Compression for Hybrid Route Planning / Gernot Veit Batz, Robert Geisberger, Dennis Luxen -- Multipath Spanners via Fault-Tolerant Spanners / Shiri Chechik, Quentin Godfroy, David Peleg -- Constant Thresholds Can Make Target Set Selection Tractable / Morgan Chopin, André Nichterlein, Rolf Niedermeier -- Faster Variance Computation for Patterns with Gaps / Fabio Cunial.

Enhancing the Computation of Distributed Shortest Paths on Real Dynamic Networks / Gianlorenzo D'Angelo, Mattia D'Emidio -- Experimental Analysis of Rumor Spreading in Social Networks / Benjamin Doerr, Mahmoud Fouz, Tobias Friedrich -- A Randomised Approximation Algorithm for the Partial Vertex Cover Problem in Hypergraphs / Mourad El Ouali, Helena Fohlin, Anand Srivastav -- Simulation-Based Analysis of Topology Control Algorithms for Wireless Ad Hoc Networks / Fabian Fuchs, Markus Völker, Dorothea Wagner -- Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability / Michael T. Goodrich, Daniel S. Hirschberg -- An Efficient Generator for Clustered Dynamic Random Networks / Robert Görke, Roland Kluge, Andrea Schumm -- Slow Down and Sleep for Profit in Online Deadline Scheduling / Peter Kling, Andreas Cord-Landwehr -- FIFO Queueing Policies for Packets with Heterogeneous Processing / Kirill Kogan, Alejandro López-Ortiz.

Includes bibliographical references and author index.

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.