References

  1. Khaled M. Alzoubi, Peng-Jun Wan & Ophir Frieder (2002): Message-optimal connected dominating sets in mobile ad hoc networks. In: Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, pp. 157–164, doi:10.1145/513800.513820.
  2. Baruch Awerbuch (1989): Distributed Shortest Paths Algorithms (Extended Abstract). In: STOC, pp. 490–500.
  3. Baruch Awerbuch, Andrew V. Goldberg, Michael Luby & Serge A. Plotkin (1989): Network Decomposition and Locality in Distributed Computation. In: FOCS, pp. 364–369.
  4. Petra Berenbrink, Colin Cooper & Zengjian Hu (2009): Energy efficient randomised communication in unknown AdHoc networks. Theor. Comput. Sci. 410(27-29), pp. 2549–2561, doi:10.1016/j.tcs.2009.02.002.
  5. Jeremy Blum, Min Ding, Andrew Thaeler & Xiuzhen Cheng (2004): Connected Dominating Set in Sensor Networks and MANETs. In: Ding-Zhu Du & PanosM. Pardalos: Handbook of Combinatorial Optimization. Springer US, pp. 329–369.
  6. John Adrian Bondy (1976): Graph Theory With Applications. Elsevier Science Ltd.
  7. Jae-Hwan Chang & Leandros Tassiulas (2004): Maximum lifetime routing in wireless sensor networks. IEEE/ACM Trans. Netw. 12(4), pp. 609–619, doi:10.1109/TNET.2004.833122.
  8. Guillaume Chelius & Eric Fleury (2005): NP-Completeness of ad hoc multicast routing problems. Technical Report RR-5665. INRIA.
  9. I. Chlamtac & S. Kutten (1985): On Broadcasting in Radio Networks–Problem Analysis and Protocol Design. Communications, IEEE Transactions on 33(12), pp. 1240–1246, doi:10.1109/TCOM.1985.1096245.
  10. Bogdan S. Chlebus, Dariusz R. Kowalski, Andrzej Pelc & Mariusz A. Rokicki (2011): Efficient Distributed Communication in Ad-Hoc Radio Networks. In: ICALP (2), pp. 613–624, doi:10.1145/1281100.1281130.
  11. Bogdan S. Chlebus, Dariusz R. Kowalski & Tomasz Radzik (2009): Many-to-Many Communication in Radio Networks. Algorithmica 54(1), pp. 118–139, doi:10.1007/s00453-007-9123-5.
  12. Marek Chrobak, Leszek Gasieniec & Wojciech Rytter (2002): Fast broadcasting and gossiping in radio networks. J. Algorithms 43(2), pp. 177–189, doi:10.1016/S0196-6774(02)00004-4.
  13. Marek Chrobak & Dariusz Kowalski (2004): The wake-up problem in multi-hop radio networks. In: 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 985–993.
  14. Ferdinando Cicalese, Fredrik Manne & Qin Xin (2006): Faster Centralized Communication in Radio Networks. In: ISAAC, pp. 339–348, doi:10.1145/1073814.1073840.
  15. Andrea Clementi, Angelo Monti, Francesco Pasquale & Riccardo Silvestri (2012): Optimal gossiping in geometric radio networks in the presence of dynamical faults. Networks 59(3), pp. 289–298, doi:10.1002/net.21451.
  16. Andrea E. F. Clementi, Angelo Monti & Riccardo Silvestri (2003): Distributed broadcast in radio networks of unknown topology. Theor. Comput. Sci. 302(1-3), pp. 337–364, doi:10.1016/S0304-3975(02)00851-4.
  17. Bevan Das & Vaduvur Bharghavan (1997): Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets. In: IEEE International Conference on Communications, pp. 376–380, doi:10.1.1.40.8504.
  18. Bilel Derbel & El-Ghazali Talbi (2010): Radio Network Distributed Algorithms in the Unknown Neighborhood Model. In: Distributed Computing and Networking, Lecture Notes in Computer Science 5935. Springer, pp. 155–166, doi:10.1007/978-3-642-11322-2_18.
  19. Ling Ding, Weili Wu, J. Willson, Hongjie Du, Wonjun Lee & Ding-Zhu Du (2011): Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks. Parallel and Distributed Systems, IEEE Transactions on 22(10), pp. 1601–1609, doi:10.1109/TPDS.2011.30.
  20. Hongwei Du, Qiang Ye, Weili Wu, Wonjun Lee, Deying Li, Ding-Zhu Du & Stephen Howard (2011): Constant approximation for virtual backbone construction with Guaranteed Routing Cost in wireless sensor networks. In: INFOCOM, pp. 1737–1744, doi:10.1109/INFCOM.2011.5934967.
  21. Devdatt Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan & Arvind Srinivasan (2003): Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. In: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, SODA '03, pp. 717–724, doi:10.1016/j.jcss.2005.04.002.
  22. Yuval Emek, Leszek Gasieniec, Erez Kantor, Andrzej Pelc, David Peleg & Chang Su (2007): Broadcasting in udg radio networks with unknown topology. In: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. ACM, pp. 195–204, doi:10.1145/1281100.1281130.
  23. Yuval Emek, Erez Kantor & David Peleg (2008): On the effect of the deployment setting on broadcasting in Euclidean radio networks. In: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, PODC '08. ACM, pp. 223–232, doi:10.1145/1400751.1400782.
  24. Pierre Fraigniaud & Emmanuel Lazard (1994): Methods and problems of communication in usual networks. Discrete Applied Mathematics 53(1–3), pp. 79–133, doi:10.1016/0166-218X(94)90180-5.
  25. R. Gandhi, A. Mishra & S. Parthasarathy (2008): Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks. Networking, IEEE/ACM Transactions on 16(4), pp. 840–851, doi:10.1109/TNET.2007.905588.
  26. M. R. Garey & David S. Johnson (1979): Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
  27. Leszek Gasieniec, David Peleg & Qin Xin (2005): Faster communication in known topology radio networks. In: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, pp. 129–137, doi:10.1145/1073814.1073840.
  28. Leszek Gąsieniec, Erez Kantor, DariuszR. Kowalski, David Peleg & Chang Su (2008): Time efficient k-shot broadcasting in known topology radio networks. Distributed Computing 21, pp. 117–127, doi:10.1007/s00446-008-0058-0.
  29. Leszek Gąsieniec, DariuszR. Kowalski, Andrzej Lingas & Martin Wahlen (2008): Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges. In: Gadi Taubenfeld: Distributed Computing, Lecture Notes in Computer Science 5218. Springer Berlin Heidelberg, pp. 274–288, doi:10.1007/978-3-540-87779-0_19.
  30. Sudipto Guha & Samir Khuller (1996): Approximation Algorithms for Connected Dominating Sets. Algorithmica 20, pp. 374–387, doi:10.1007/PL00009201.
  31. P. Gupta & P.R. Kumar (2000): The capacity of wireless networks. Information Theory, IEEE Transactions on 46(2), pp. 388–404, doi:10.1109/18.825799.
  32. Piyush Gupta & P. R. Kumar (2000): The capacity of wireless networks. IEEE TRANSACTIONS ON INFORMATION THEORY 46(2), pp. 388–404, doi:10.1109/18.825799.
  33. Bernhard Haeupler & Fabian Kuhn (2012): Lower Bounds on Information Dissemination in Dynamic Networks. In: DISC, pp. 166–180, doi:10.1007/978-3-642-33651-5_12.
  34. Magnús M. Halldórsson & Pradipta Mitra (2012): Distributed connectivity of wireless networks. In: PODC, pp. 205–214, doi:10.1145/2332432.2332469.
  35. F. Harary & B. Raghavachari (1997): The e-mail gossip number and the connected domination number. Applied Mathematics Letters 10(4), pp. 15 – 17, doi:10.1016/S0893-9659(97)00052-9.
  36. Sandra M. Hedetniemi, Stephen T. Hedetniemi & Arthur L. Liestman (1988): A survey of gossiping and broadcasting in communication networks. Networks 18(4), pp. 319–349, doi:10.1002/net.3230180406.
  37. T. Jurdzinski, D.R. Kowalski & G. Stachowiak (2012): Distributed Deterministic Broadcasting in Wireless Networks under the SINR Model. ArXiv e-prints, doi:10.1145/1210.1804.
  38. Tomasz Jurdzinski & Dariusz R. Kowalski (2012): Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks. In: DISC, pp. 106–120, doi:10.1007/978-3-642-33651-5_8.
  39. Tomasz Jurdzinski & Dariusz R. Kowalski (2012): Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks. In: DISC, pp. 106–120, doi:10.1007/978-3-642-33651-5_8.
  40. Tomasz Jurdzinski & Dariusz R. Kowalski (2012): On the Complexity of Distributed Broadcasting and MDS Construction in Radio Networks. In: OPODIS, pp. 209–223, doi:10.1007/978-3-642-35476-2_15.
  41. Tomasz Jurdzinski, Miroslaw Kutylowski & Jan Zatopianski (2002): Efficient algorithms for leader election in radio networks. In: Proceedings of the twenty-first annual symposium on Principles of distributed computing, PODC '02, pp. 51–57, doi:10.1145/571825.571833.
  42. Donghyun Kim, Yiwei Wu, Yingshu Li, Feng Zou & Ding-Zhu Du (2009): Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks. Parallel and Distributed Systems, IEEE Transactions on 20(2), pp. 147–157, doi:10.1109/TPDS.2008.74.
  43. Dariusz R. Kowalski & Andrzej Pelc (2007): Optimal deterministic broadcasting in known topology radio networks. Distrib. Comput. 19(3), pp. 185–195, doi:10.1007/s00446-006-0007-8.
  44. Fabian Kuhn & Rogert Wattenhofer (2003): Constant-time distributed dominating set approximation. In: Proceedings of the twenty-second annual symposium on Principles of distributed computing, PODC '03, pp. 25–32, doi:10.1145/872035.872040.
  45. Andreas Lehner, Cristina Rico Garcia, Eugen Wige & Thomas Strang (2009): A multi-broadcast communication system for high dynamic vehicular ad-hoc networks. In: ICUMT, pp. 1–6, doi:10.1504/IJVICS.2011.044267.
  46. Liron Levin, Michael Segal & Hanan Shpungin (2013): Interference-free energy efficient scheduling in wireless ad hoc networks. Ad Hoc Networks 11(1), pp. 201–212, doi:10.1016/j.adhoc.2012.05.004.
  47. Ou Liang, Y. Ahmet Sekercioglu & Nallasamy Mani (2006): A survey of multipoint relay based broadcast schemes in wireless ad hoc networks. Commun. Surveys Tuts. 8(4), pp. 30–46, doi:10.1109/COMST.2006.283820.
  48. Ritesh Maheshwari, Shweta Jain & Samir R. Das (2008): A measurement study of interference modeling and scheduling in low-power wireless networks. In: Proceedings of the 6th ACM conference on Embedded network sensor systems, pp. 141–154, doi:10.1145/1460412.1460427.
  49. S. A. M. Makki & George Havas (1996): Distributed Algorithms for Depth-First Search. Inf. Process. Lett. 60(1), pp. 7–12, doi:10.1016/S0020-0190(96)00141-X.
  50. Gianluca De Marco (2010): Distributed Broadcast in Unknown Radio Networks. SIAM J. Comput. 39(6), pp. 2162–2175, doi:10.1137/080733826.
  51. Michael J. Mcglynn (2001): Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks. In: In Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 137–145, doi:10.1145/501416.501435.
  52. K. Nakano & S. Olariu (2000): Randomized Leader Election Protocols for Ad-hoc Networks. In: SIROCCO’2000, Carleton Scientific, pp. 253–267, doi:10.1.1.36.8032.
  53. Koji Nakano & Stephan Olariu (2000): Randomized Leader Election Protocols in Radio Networks with no Collision Detection. In: Gerhard Goos, Juris Hartmanis, Jan van Leeuwen, D. Lee & Shang-Hua Teng: Algorithms and Computation, Lecture Notes in Computer Science 1969. Springer Berlin Heidelberg, pp. 101–213, doi:10.1007/3-540-40996-3_31.
  54. Koji Nakano, Stephan Olariu, Ieee Computer Society & Ieee Computer Society (2000): Randomized Initialization Protocols for Ad Hoc Networks. IEEE Transactions on Parallel and Distributed Systems 11, pp. 749–759, doi:10.1109/71.877833.
  55. Kaveh Pahlavan & Allen H. Levesque (1995): Wireless information networks. Wiley-Interscience.
  56. Dragan Petrovic, Rahul C. Shah, Kannan Ramchandran & Jan Rabaey (2003): Data Funneling: Routing with Aggregation and Compression for Wireless Sensor Networks. In: International Conference on Communications, pp. 156–162, doi:10.1.1.66.9838.
  57. Frank Reichenbach, Ralf Salomon & Dirk Timmermann (2006): Distributed obstacle localization in large wireless sensor networks. In: Proceedings of the international conference on Wireless communications and mobile computing, pp. 1317–1322, doi:10.1145/1143549.1143814.
  58. Anna Scaglione & Sergio D. Servetto (2005): On the Interdependence of Routing and Data Compression in Multi-Hop Sensor Networks. Wireless Networks 11(1-2), pp. 149–160, doi:10.1007/s11276-004-4752-y.
  59. Roberto Solis-Oba (1998): 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves. In: ESA, pp. 441–452, doi:10.1.1.46.3286.
  60. Guang Tan, Stephen A. Jarvis, James W. J. Xue & Simon D. Hammond (2007): Distributed Broadcast Scheduling in Mobile Ad Hoc Networks with Unknown Topologies. In: IPDPS, pp. 1–7, doi:10.1109/IPDPS.2007.370591.
  61. P. Venkateswaran, Rahul Ghosh, Aritra Das, S. K. Sanyal & Rabindranath Nandi (2006): An Obstacle Based Realistic Ad-Hoc Mobility Model for Social Networks. JNW 1, pp. 37–44, doi:10.4304/jnw.1.2.37-44.
  62. Peng-Jun Wan, Khaled M. Alzoubi & Ophir Frieder (2004): Distributed construction of connected dominating set in wireless ad hoc networks. Mob. Netw. Appl. 9(2), pp. 141–149, doi:10.1023/B:MONE.0000013625.87793.13.
  63. Jie Wu & Hailan Li (1999): On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, pp. 7–14, doi:10.1145/313239.313261.
  64. Weili Wu, Hongwei Du, Xiaohua Jia, Yingshu Li & Scott C.-H. Huang (2006): Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theor. Comput. Sci. 352(1), pp. 1–7, doi:10.1016/j.tcs.2005.08.037.
  65. Dongxiao Yu, Qiang-Sheng Hua, Yuexuan Wang, Haisheng Tan & FrancisC.M. Lau (2012): Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model. In: Structural Information and Communication Complexity 7355. Springer Berlin Heidelberg, pp. 111–122, doi:10.1007/978-3-642-31104-8_10.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org