Reading Group Seminar: Summer 2007

Tentative Schedule:

meet on Tuesdays 2:00pm-4:00pm ITE 201A but some talks may be at a different place and time.

Date	Discussion Leader	Paper
May 29th	Yoo-Ah Kim	Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks.,
June 5th	Chadi Kari	Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs
June 12th	Matthew Coolbeth	Constant density spanners for wireless ad-hoc networks
June 19^th	Hieu Dinh	Centralized asynchronous broadcast in radio networks
July 26^th	Hang Dinh	Average-time complexity of gossiping in radio networks
July 6^th	Matthew Coolbeth	FLSS: a fault-tolerant topology control algorithm for wireless networks
July 13^th	Chadi Kari	Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks
July 24^th	Yoo-Ah Kim	Approximating node connectivity problems via set covers
July 31^st	Chadi Kari	Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks (continued)

For additional information send email to Yoo-Ah Kim.

---

Additional Paper list

Multicast Capacity of Large Scale Wireless Ad Hoc Networks ACM MobiCom 2007 Xiang-Yang Li, Shao-Jie Tang and Ophir Frieder

Distributed Low-Cost Weighted Backbone Formation for Wireless Ad Hoc Networks, ACM MobiHoc, 2005 Yu Wang and WeiZhao Wang and Xiang-Yang Li

A Dominating and Absorbent Set in a Wireless Ad-hoc Network with Different Transmission Ranges, mobihoc2007 Myung Ah Park , James Willson, Chen Wang , My Thai , Weili Wu, Andras Farago

Complexity in Geometric SINR (Mobihoc 2007) Olga Goussevskaia, Yvonne Anne Oswald, Roger Wattenhofer (ETH Zurich)

Cross-Layer Latency Minimization in Wireless Networks with SINR Constraints (MOBIhoc 2007) Deepti Chafekar, V.S. Anil Kumar , Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan (University of Maryland)

The multicast capacity of large multihop wireless networks (Mobihoc 2007) Srinivas Shakkottai, Xin Liu, R. Srikant

Scheduling Algorithms for Multi-Carrier Wireless Data Systems (Mobicom 2007) Matthew Andrews &Lisa Zhang (Bell Laboratories)

Reading List

1) Broadcasting/Gossiping in wireless networks

- Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks., R. Gandhi, S. Parthasarathy, and A. Mishra. Mobihoc 2003

- Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs, Christoph Ambühl, Thomas Erlebach, Matus Mihalak, Marc Nunkesser, APPROX 2006

- Constant density spanners for wireless ad-hoc networks, Kishore Kothapalli, Christian Scheideler, Melih Onus, Andrea W. Richa.. SPAA 2005
(Efficient broadcasting and gathering in wireless ad-hoc networks. K. Kothapalli, M. Onus, A. Richa and C. Scheideler., I-SPAN, 2005)

- Average-time complexity of gossiping in radio networks, Bogdan S. Chlebus, D.R. Kowalski and M.A. Rokicki, SIROCCO, 2006

- Centralized asynchronous broadcast in radio networks, Bogdan S. Chlebus, M.A. Rokicki, Theoretical Computer Science (SIROCCO 2004)

- Upper Bounds on Broadcasting Time in UDG Radio Networks with Unknown Topology, , Yuval Emek, Leszek Gasieniec, Erez Kantor,Andrzej Pelc, David Peleg, Chang Su , PODC 2007

- Broadcasting and Gossiping in Radio Networks, , Ding Liu and Manoj Prabhakaran, COCOON 2002

- Nearly Constant Approximation for Data Aggregation Scheduling in Wireless Sensor Networks. Scott C.H. Huang, Peng-Jun Wan, Chinh T. Vu, Yingshu Li, and Frances Yao, Infocom 2007.

More related papers:

- Smart Gossip: A Probabilistic Framework for Broadcasting in Sensor Networks, Pradeep Kyasanur, Romit Roy Choudhury, Indranil Gupta, MASS 2006

- Minimum Latency Broadcasting in Multi-Radio Multi-Channel Multi-Rate Wireless Mesh Networks, Junaid Qadir, Chun Tung Chou, Archan Misra, SECON 2006

- A Constant Approximation Algorithms for Interference Aware Broadcast in Multihop Wireless Networks," with Z. Chen, C. Qiao, and T. Lee. INFOCOM 2007

2) Fault-tolerant topology control

- Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, MohammadTaghi Hajiaghayi, Nicole Immorlica, Vahab S. Mirrokni, Mobicom 2003

- Relay placement for higher order connectivity in sensor networks, A. Kashyap, S. Khuller and M. Shayman, Infocom 2006

- A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph, Hiroshi Nagamochi and Toshihide Ibaraki, Algorithmica, 1992

- FLSS: a fault-tolerant topology control algorithm for wireless networks, Ning Li, Jennifer C. Hou, Mobicom 2004

- Approximating Minimum-size k-Connected Spanning Subgraphs via Matching, Joseph Cheriyan, Ramakrishna Thurimella, SIAM J of Computing, 2000

- Sub-Linear Distributed Algorithms for Sparse Certificates and Biconnected Components, Ramakrishna Thurimella, J. of Algorithm 1997

- Distributed algorithms for sparse k-connectivity certificates, Esther Jennings and Lenka Motyckova, PODC 96

- Improved approximation algorithms for uniform connectivity problems, S. Khuller, B. Raghavachari, J. Algorithms, 1996

Miscellaneous

- Packing to Angles and Sectors, Piotr Berman, Jieun Jeong, Shiva Kasiviswanathan, and Bhuvan Urgaonkar,  SPAA 2007. 

- Maximizing Throughput in Wireless Networks via Gossiping, E. Modiano, D. Shah, and G. Zussman, Proc. ACM SIGMETRICS / IFIP Performance 2006.

---