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.)

Submitted:

  • L. Ritchie, M. Onus, A. Richa and M. Reisslein. Physical Carrier Sense Based Mechanisms for Efficient Broadcast and Convergecast in Wireless Ad Hoc Networks.

    • Journal Papers:

  • S. Oh, Y. Huh, B. Kulapala, A. Richa and M. Reisslein. Continuous-Time Collaborative Prefetching of Continuous Media. To appear in IEEE Transactions on Broadcasting.
  • 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. To appear in journal of Telecommunication Systems (invited submission).
  • 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.

    • Reviewed Conference Papers:

  • 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), 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'06.
  • 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.

    • Chapters:

  • A.W. Richa and C. Scheideler. Overlay Networks for Peer-to-peer systems. To appear in Handbook on Approximation Algorithms and Metaheuristics, edited by S. Sahni.
  • 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", edited by P. Pardalos, S. Rajasekaran, and J. Rolim, pages 255-305, Kluwer Press.
    • This page has been partially updated on 03/29/06.