Selected 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:

  • Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Taeubig. Brief Announcement: On the Time Complexity of Distributed Topological Self-Stabilization. To appear in Proceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2009.
  • 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.
  • 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:

  • 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:

    ... This page has been partially updated on 09/10/09.