Selected Publications

Please check dblp for a more up-to-date list of my publications.


(In most of the publications below -- i.e., in all publications on Theory/Algorithms conferences and journals -- the list of authors appears in alphabetical order, and not with respect to the contribution of each author to the paper.)

Reviewed Conference Papers:

  • Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. Self-Stabilizing Leader Election for Single-Hop Wireless Networks despite Jamming. In Proceedings of the 12th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2011.
  • Andréa W. Richa, Stefan Schmid, Christian Scheideler, and Jin Zhang. Competitive and Fair Medium Access despite Reactive Jamming. To appear in Proceedings of the IEEE 31st International Conference on Distributed Computing Systems (ICDCS), pages 507-516, 2011.
  • Goran Konjevod, Andréa W. Richa, Donglin Xia, Ling Zhou. Brief Announcement: Randomized compact routing in decomposable metrics. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 351-352, 2011.
  • Andréa W. Richa, Christian Scheideler, Phillip Stevens. Self-Stabilizing De Bruijn Networks. In Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 416-430, 2011.
  • Andréa W. Richa, Stefan Schmid, Christian Scheideler, and Jin Zhang. A Jamming Resistant MAC Protocol for Multi-Hop Wireless Networks. In Proceedings of the 24th International Symposium on Distributed Computing (DISC), pages 179-193, 2010.
  • Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, Andrea Richa. Broadcasting in Radio Networks with Unreliable Communication. In Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC), July, 2010.
  • Andréa W. Richa, Stefan Schmid, Christian Scheideler, and Jin Zhang. Brief Announcement: A Jamming Resistant MAC Protocol for Multi-Hop Wireless Networks. In Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC), July, 2010.
  • Melih Onus and Andréa W. Richa. Parameterized Minimum Degree Publish-Subscribe Overlay Network Design. In Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS), June, 2010. Acceptance rate: 14%.
  • Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Taeubig. On the Time Complexity of Distributed Topological Self-Stabilization. In Proceedings of LATIN'10, pages 294-305, 2010.
  • Riko Jacob, Andréa W. Richa, Christian Scheideler, Stefan Schmid, Hanjo Taeubig. A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. In Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pages 131-140, 2009.
  • Melih Onus, Andréa W. Richa. Minimum maximum degree topic-based publish-subscribe overlay network design. In Proceedings of the 28th Annual IEEE Conference on Computer Communications (INFOCOM), 2009.
  • Melih Onus, Andréa W. Richa. Brief announcement: parameterized maximum and average degree approximation in topic-based publish-subscribe overlay network design. Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 39-40, 2009.
  • Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Taeubig. Brief Announcement: On the Time Complexity of Distributed Topological Self-Stabilization. In Proceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 781-782, 2009.
  • Goran Konjevod, Andréa W. Richa, Donglin Xia.Dynamic Routing and Location Services in Low Doubling Dimension . In Proceedings of the 22nd International Symposium on Distributed Computing (DISC), pages 379-393, 2008.
  • Christian Scheideler, Andrea W. Richa, and Paolo Santi. An O(log n) Dominating Set Protocol for Wireless Ad-Hoc Networks under the Physical Interference Model. In Proceedings of the 9th ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pages 91-100, 2008.
  • Baruch Awerbuch, Andrea W. Richa, and Christian Scheideler,. A Jamming-Resistant MAC Protocol for Single-Hop Wireless Networks. In Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pages 45-54, 2008.
  • Goran Konjevod, Andréa W. Richa, Donglin Xia.Brief Announcement: Dynamic Routing and Location Services in Low Doubling Dimension . In Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), 2008.
  • Goran Konjevod, Andréa W. Richa, Donglin Xia, Hai Yu.Compact routing with slack in low doubling dimension . In Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pages 71-80, 2007.
  • Goran Konjevod, Andréa W. Richa, and Donglin Xia.Optimal scale-free compact routing schemes in doubling networks . In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 939-948, 2007.
  • Melih Onus, Andrea W. Richa, and Christian Scheideler,. Linearization: Locally Self-Stabilizing Sorting in Graphs. In Proceedings of ALENEX'07.
  • G. Konjevod, A.W. Richa, D. Xia. Optimal Stretch Name-Independent Compact Routing in Doubling Metrics . In Proceedings of 18th ACM Symposium on Principles of Distributed Computing (PODC), pages 198-207, 2006.
  • T-H. H. Chan, D. Xia, G. Konjevod, A. Richa. A Tight Lower Bound for Steiner Point Removal Problem on Trees , In Proceedings of APPROX-RANDOM 2006: 70-81, 2006.
  • D. Xia, G. Konjevod, and A. Richa. On sampling in higher-dimensional peer-to-peer systems. In Proceedings of LATIN'06, pages 641-652, 2006.
  • Kishore Kothapalli, Christian Scheideler, Melih Onus, Andrea W. Richa. Constant density spanners for wireless ad-hoc networks. In Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 116-125, 2005.
  • K. Kothapalli, M. Onus, A. Richa and C. Scheideler. Efficient Broadcasting and Gathering in Wireless Ad Hoc Networks. In Proceedings of the IEEE International Symposium on Parallel Architectures, Algorithms and Networks(ISPAN), pages 346-351, 2005.
  • Liang Yang, Tushar Gohad, Pavel Ghosh, Devesh Sinha, Arunabha Sen, Andrea Richa. Resource mapping and scheduling for heterogeneous network processors. In Proceedings of the 2005 ACM Symposium on Architecture for networking and communications systems (ANCS), 2005.
  • A. Ferreira, S. Perennes, A.W. Richa, H. Rivano, and N. Stier. Models, complexity, and algorithms for the design of multifiber WDM networks. In Proceedings of IEEE International Conference on Telecommunications (ICT), pages 12--18, 2003.
  • H. Huang, A.W. Richa, and M. Segal. Approximation Algorithms for the Mobile Piercing Set Problem with Applications to Clustering. In Proceedings of 6th ACM Workshop on Discrete Algorithms and Method for Communication (DIAL-M), pages 52-61, August 2002.
  • A. Ferreira, S. Perennes, A.W. Richa, H. Rivano, and N. Stier. On the design of multifiber WDM networks. In Proceedings of AlgoTel'02, pages 25--32, France, 2002.
  • G. Konjevod, S. Oh, and A.W. Richa. Finding Most-Sustainable Paths in Networks with Time-Dependent Edge-Reliabilities . In Proceedings of Latin American Theoretical INformatics (LATIN), pages 435-450, April 2002.
  • A.W. Richa, K. Obraczka, and A. Sen. Application-oriented Self-organizing Hierarchical Clustering in Dynamic Networks. In Proceedings of 1st ACM Workshop on Principles of Mobile Computing (POMC), pages 57-65, August 2001.
  • R. Rajaraman, A.W. Richa, B. Voecking, and G. Vuppuluri. A data tracking scheme for general networks. In Proceedings of 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 247-254, July 2001.
  • A. W. Richa, A. Sen, B. H. Shen, and S. Bandyopadhyay. On Routing and Wavelength Assignment in Optical Networks. In Proceedings of the Thirty-Eighth Annual Allerton Conference on Communication, Control and Computing to be held at University of Illinois, October 2000.
  • S. Rao and A. W. Richa. New Approximation Techniques for Some Ordering Problems. In Proceedings of Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 211-218, January 1998.
  • R. Cole, B. M. Maggs, F. Meyer auf der Heide, M. Mitzenmacher, A. W. Richa, K. Schroder, R. K. Sitaraman, and B. Vocking. Randomized Protocols for Low-Congestion Circuit Routing in Multistage Interconnection Networks. In Proceedings of the 30th Annual Symposium on the Theory of Computing (STOC), pages 378-388, May 1998.
  • R. Cole, A. Frieze, B. M. Maggs, M. Mitzenmacher, A. W. Richa, R. K. Sitaraman, and E. Upfal. On Balls and Bins with Deletions. In Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), number 1518 in Lecture Notes in Computer Science, pages 145-158, October 1998.
  • C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment, In Proceedings of Parallel Algorithms and Architectures (SPAA), pages 311-320, June 1997.
  • B. Ghosh, F. T. Leighton, B. M. Maggs, S. Muthukrishan, C. G. Plaxton, R. Rajaraman, A. W. Richa, R. E. Tarjan, and D. Zuckerman. Tight Analysis of Two Local Load Balancing Algorithms, In Proceedings of the 27th Annual Symposium on the Theory of Computing (STOC), Las Vegas, pages 548-558, May 1995.

    • Journal Papers:

  • Melih Onus and Andrea W. Richa. Minimum Degree Publish-Subscribe Overlay Network Design. IEEE Transactions on Networking, volume 19(5), pages 1331-1343, 2011.
  • Luke Ritchie, Sapna Deval, Martin Reisslein, and Andrea Richa. Evaluation of Physical Carrier Sense Based Backbone Construction and Maintenance as well as Broadcast and Convergecast in ad hoc networks, Ad Hoc Networks, 7(7):1347-1369, September 2009.
  • Sapna Deval, Luke Ritchie, Martin Reisslein, and Andrea W. Richa. Evaluation of Physical Carrier Sense Based Backbone Maintenance in Mobile Ad Hoc Networks, International Journal of Vehicular Technology, vol. 2009, Article ID 958056, 13 pages, 2009. doi:10.1155/2009/958056.
  • S. Oh, Y. Huh, B. Kulapala, A. Richa and M. Reisslein. Continuous-Time Collaborative Prefetching of Continuous Media. In IEEE Transactions on Broadcasting, volume 54, issue 1, pages 36-52, 2008.
  • H.-S. Yang, L. Ritchie, A. Richa and M. Reisslein. MANET Routing with Provably Low Complexity Through Constant Density Clustering and Route Request Broadcast, Wireless Personal Communications, Volume 43, Number 2, pages 605-621, October 2007.
  • L. Ritchie, H.-S. Yang, A.W. Richa, and M. Reisslein. Cluster Overlay Broadcast (COB): MANET Routing with Complexity Polynomial in Source-Destination Distance. IEEE Transactions on Mobile Computing, Volume 5, Issue 6, pages 653 - 667, June 2006.
  • Hai Huang, Andréa W. Richa, Michael Segal. Dynamic Coverage in Ad-Hoc Sensor Networks. ACM Baltzer Journal on Mobile Networks and Applications (MONET) 10(1-2): 9-17 (2005).
  • S. Oh, Y. Huh, B. Kulapala, G. Konjevod, A.W. Richa, M. Reisslein. A modular algorithm-theoretic framework for the fair and efficient collaborative prefetching of continuous media. IEEE Transactions on Broadcasting, volume 51 issue 2, pages 200- 215, 2005.
  • S. Rao and A. W. Richa. New Approximation Techniques for Some Linear Ordering Problems. SIAM Journal of Computing, Volume 34, Number 2, pages 388 - 404, 2005.
  • H. Huang, A.W. Richa, and M. Segal. Approximation Algorithms for the Mobile Piercing Set Problem with Applications to Clustering in Ad-Hoc Networks. ACM Baltzer Journal on Mobile Networks and Applications (MONET), Volume 9, Number 2, pages 151-161, April 2004.
  • A. Ferreira, S. Perennes, A.W. Richa, H. Rivano, and N. Stier. Models, complexity, and algorithms for the design of multifiber WDM networks. Telecommunication Systems 24(2-4): 123-138 (2003).
  • F. T. Leighton, B. M. Maggs, and A. W. Richa. Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules, Combinatorica, 19(2):1--27, 1999. A preliminary version of this paper appeared as Technical Report CMU-CS-96-152, Carnegie Mellon University, Pittsburgh, PA, 1996.
  • C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment, Theory of Computing Systems, 32:241-280, 1999. A preliminary version of this paper appeared in Proceedings of Parallel Algorithms and Architectures (SPAA), pages 311-320, June 1997.
  • B. Ghosh, F. T. Leighton, B. M. Maggs, S. Muthukrishan, C. G. Plaxton, R. Rajaraman, A. W. Richa, R. E. Tarjan, and D. Zuckerman. Tight Analysis of Two Local Load Balancing Algorithms. SIAM Journal on Computing, 29(1), pages 29-64, 1999. A preliminary version of this paper appeared in Proceedings of the 27th Annual Symposium on the Theory of Computing (STOC), Las Vegas, pages 548-558, May 1995.

    • Chapters:

  • A.W. Richa and C. Scheideler. Overlay Networks for Peer-to-peer systems. In Teofilo Gonzales (Editor), Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall / CRC Press, Chapter 72, 2007.
  • M. Mitzenmacher, A. Richa, and R. Sitaraman. The power of two random choices: A survey of the techniques and results. In "Handbook of Randomized Computing, volume I", P. Pardalos, S. Rajasekaran, and J. Rolim (eds.), pages 255-305, Kluwer Press.

    • Submitted:

  • Andrea W. Richa, Stefan Schmid, Christian Scheideler, and Jin Zhang. A Jamming Resistant MAC Protocol for Multi-Hop Wireless Networks. Submitted to journal Distributed Computing, invited submission (selected papers from DISC 2010), 2010.
  • Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Taeubig. On the Time Complexity of Distributed Topological Self-Stabilization. Submitted to journal ACM Transactions on Algorithms, August 2010.
  • Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Taeubig. A Polylogarithmic Time Construction for Distributed Self-Stabilizing Skip Graphs. Submitted to journal SIAM Journal on Computing (SICOMP), August 2010.
  • more...
    • This page has been partially updated on 11/18/11.