Skip to main content

Papers accepted to track C of ICALP 2012

  • Ran Gelles, Rafail Ostrovsky and Kina Winoto. Multi-User Equality Testing and Its Applications
  • Marcel Ochel, Klaus Radke and Berthold Voecking. Online Packing with Gradually Improving Capacity Estimations with Applications to Network Lifetime Maximization
  • Michael Goodrich and Michael Mitzenmacher. Anonymous Card Shuffling and its Applications to Parallel Mixnets
  • Adrian Kosowski, Bi Li, Nicolas Nisse and Karol Suchan. k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth
  • Yoann Dieudonne and Andrzej Pelc. Deterministic network exploration by anonymous silent agents with local traffic reports
  • Fedor Fomin, Petr Golovach, Jesper Nederlof and Michał Pilipczuk. Minimizing Rosenthal Potential in Multicast Games
  • Ilias Diakonikolas, Christos Papadimitriou, George Pierrakos and Yaron Singer. Efficiency-Revenue Trade-offs in Auctions
  • Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald and He Sun. Counting Arbitrary Subgraphs in Data Streams
  • Piotr Krysta and Berthold Voecking. Online Mechanism Design (Randomized Rounding on the Fly)
  • Ning Chen, Xiaotie Deng, Hongyang Zhang and Jie Zhang. Incentive Ratios of Fisher Markets
  • Leonid Barenboim. On the Locality of NP-Complete Problems
  • Khaled Elbassioni. A QPTAS for $\eps$-Envy-Free Profit-Maximizing Pricing on Line Graphs
  • Reuven Bar-Yehuda, Erez Kantor, Shay Kutten and Dror Rawitz. Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs
  • Nishanth Chandran, Juan Garay and Rafail Ostrovsky. Edge Fault Tolerance on Sparse Networks
  • Elias Koutsoupias and Katia Papakonstantinopoulou. Contention issues in congestion games
  • David Peleg, Liam Roditty and Elad Tal. Distributed Algorithms for Network Diameter and Girth
  • Navendu Jain, Ishai Menache, Joseph Naor and F. Bruce Shepherd. Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks
  • Andrew Berns, Sriram Pemmaraju and James Hegeman. Super-Fast Distributed Algorithms for Metric Facility Location
  • Luca Gugelmann, Konstantinos Panagiotou and Ueli Peter. Hyperbolic Random Graphs: Degree Sequence and Clustering
  • Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach and Maurizio Patrignani. Computational Complexity of Traffic Hijacking under BGP and S-BGP
  • Adam Groce, Jonathan Katz, Aishwarya Thiruvengadam and Vassilis Zikas. Byzantine Agreement with a Rational Adversary
  • Kshipra Bhawalkar, Jon Kleinberg, Kevin Lewi, Tim Roughgarden and Aneesh Sharma. Preventing Unraveling in Social Networks: The Anchored k-Core Problem