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