{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:55:58Z","timestamp":1725558958163},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241324"},{"type":"electronic","value":"9783540305590"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30559-0_2","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T19:01:42Z","timestamp":1278097302000},"page":"20-32","source":"Crossref","is-referenced-by-count":1,"title":["Wireless Networking: Graph Theory Unplugged"],"prefix":"10.1007","author":[{"given":"Roger","family":"Wattenhofer","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Dolev, D., Malkhi, D.: LLS: A Locality Aware Location Service for Mobile Ad Hoc Networks. In: Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M) (2004)","DOI":"10.1145\/1022630.1022643"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Alzoubi, K., Wan, P.-J., Frieder, O.: Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks. In: Proc. ACM Int. Symposium on Mobile ad hoc networking & computing (MobiHoc), EPFL Lausanne, Switzerland, pp. 157\u2013164 (2002)","DOI":"10.1145\/513800.513820"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Peleg, D.: Concurrent online tracking of mobile users. In: SIGCOMM, pp. 221\u2013233 (1991)","DOI":"10.1145\/115992.116013"},{"key":"2_CR4","unstructured":"Beutel, J.: Geolocation in a Picoradio Environment. Master Thesis, ETH Zurich and UC Berkeley (1999)"},{"key":"2_CR5","unstructured":"Beutel, J., Kasten, O., Ringwald, M.: BTnodes \u2013 A Distributed Platform for Sensor Nodes. In: Prof. of the ACM Conference on Embedded Networked Sensor Systems (SenSys) (2003)"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Bischoff, R., Wattenhofer, R.: Analyzing Connectivity-Based Multi-Hop Ad- Hoc Positioning. In: Proc. of the Second Annual IEEE International Conference on Pervasive Computing and Communications (PerCom) (2004)","DOI":"10.1109\/PERCOM.2004.1276855"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with Guaranteed Delivery in ad hoc Wireless Networks. In: Proc. of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M), pp. 48\u201355 (1999)","DOI":"10.1145\/313239.313282"},{"issue":"1-2","key":"2_CR8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H. Breu","year":"1998","unstructured":"Breu, H., Kirkpatrick, D.G.: Unit Disk Graph Recognition is NP-hard. Comput. Geom. Theory Appl.\u00a09(1-2), 3\u201324 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Burkhart, M., von Rickenbach, P., Wattenhofer, R., Zollinger, A.: Does topology control reduce interference? In: Proc. ACM Int. Symposium on Mobile ad hoc networking & computing (MobiHoc) (2004)","DOI":"10.1145\/989459.989462"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Busch, C., Surapaneni, S., Tirthapura, S.: Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks. In: 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2003)","DOI":"10.1145\/777412.777446"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Blough, D.M., Leoncini, M., Resta, G., Santi, P.: The k-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks. In: Proc. ACM Int. Symposium on Mobile ad hoc networking & computing (MobiHoc) (2003)","DOI":"10.1145\/778415.778433"},{"issue":"4","key":"2_CR12","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A Threshold of ln n for Approximating Set Cover. Journal of the ACM (JACM)\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM (JACM)"},{"key":"2_CR13","unstructured":"Fussen, M., Wattenhofer, R., Zollinger, A.: On Interference Reduction in Sensor Networks. Technical Report 453, Department of Computer Science, ETH Zurich (2004)"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Gafni, E.M., Bertsekas, D.P.: Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE Transactions on Communication\u00a029 (1981)","DOI":"10.1109\/TCOM.1981.1094876"},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1145\/378583.378666","volume-title":"Proc. 17 th Annual Symposium on Computational Geometry (SCG)","author":"J. Gao","year":"2001","unstructured":"Gao, J., Guibas, L., Hershberger, J., Zhang, L., Zhu, A.: Discrete Mobile Centers. In: Proc. 17 th Annual Symposium on Computational Geometry (SCG), pp. 188\u2013196. ACM Press, New York (2001)"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Hill, J., Szewczyk, R., Woo, A., Hollar, S., Culler, D.E., Pister, K.S.J.: System architecture directions for networked sensors. In: Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 93\u2013104 (2000)","DOI":"10.1145\/378993.379006"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Jia, L., Rajaraman, R., Scheideler, C.: On Local Algorithms for Topology Control and Routing in Ad Hoc Networks. In: Proc. of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) (2003)","DOI":"10.1145\/777412.777447"},{"key":"2_CR18","unstructured":"Jia, L., Rajaraman, R., Suel, R.: An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In: Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pp. 33\u201342 (2001)"},{"key":"2_CR19","unstructured":"Kawadia, V., Kumar, P.R.: Power control and clustering in ad hoc networks. In: Proc. of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) (2003)"},{"key":"2_CR20","unstructured":"Kranakis, E., Singh, H., Urrutia, J.: Compass Routing on Geometric Networks. In: Proc. 11th Canadian Conference on Computational Geometry (CCCG), Vancouver, August 1999, pp. 51\u201354 (1999)"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Initializing Newly Deployed Ad Hoc and Sensor Networks. In: Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MobiCom) (2004)","DOI":"10.1145\/1023720.1023746"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Unit Disk Graph Approximation. In: Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M) (2004)","DOI":"10.1145\/1022630.1022634"},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proc. of the 23rd ACM Symposium on Principles of Distributed Computing (PODC) (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: Constant-Time Distributed Dominating Set Approximation. In: Proc. of the 22nd ACM Symposium on the Principles of Distributed Computing (PODC) (2003)","DOI":"10.1145\/872035.872040"},{"key":"2_CR25","unstructured":"Kuhn, F., Wattenhofer, R.: Distributed Combinatorial Optimization. Technical Report 426, Department of Computer Science, ETH Zurich (2003)"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric Routing: Of Theory and Practice. In: Proc. of the 22 nd ACM Symposium on the Principles of Distributed Computing (PODC) (2003)","DOI":"10.1145\/872035.872044"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically optimal geometric mobile ad-hoc routing. In: Proc. of the International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M), Atlanta, Georgia, USA (September 2002)","DOI":"10.1145\/570810.570814"},{"key":"2_CR28","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R., Zollinger, A.: Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing. In: Proc. ACM Int. Symposium on Mobile ad hoc networking & computing (MobiHoc) (2003)","DOI":"10.1145\/778415.778447"},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"Meyer auf der Heide, F., Schindelhauer, C., Volbert, K., Grunewald, M.: Energy, congestion and dilation in radio networks. In: Proc. of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA (2002)","DOI":"10.1145\/564870.564910"},{"key":"2_CR30","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., O\u2019Dell, R., Wattenhofer, M., Wattenhofer, R.: Virtual Coordinates for Ad hoc and Sensor Networks. In: Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M) (2004)","DOI":"10.1145\/1022630.1022633"},{"key":"2_CR31","doi-asserted-by":"crossref","unstructured":"Navas, J.C., Imielinski, T.: GeoCast \u2013 Geographic Addressing and Routing. In: Proceedings of the Annual International Conference on Mobile Computing and Networking (MobiCom), pp. 66\u201376 (1997)","DOI":"10.1145\/262116.262132"},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Prakash, R.: Unidirectional Links Prove Costly in Wireless Ad-Hoc Networks. In: Proc. of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M) (1999)","DOI":"10.1145\/313239.313263"},{"key":"2_CR33","doi-asserted-by":"crossref","unstructured":"Rao, A., Papadimitriou, C., Ratnasamy, S., Shenker, S., Stoica, I.: Geographic Routing without Location Information. In: Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MobiCom) (2003)","DOI":"10.1145\/938985.938996"},{"key":"2_CR34","unstructured":"Schiller, J., et al.: The scatterweb project: See for more details, http:\/\/www.scatterweb.net"},{"key":"2_CR35","doi-asserted-by":"crossref","unstructured":"Wang, Y., Li, X.-Y.: Localized Construction of Bounded Degree Planar Spanner. In: Proc. of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing (2003)","DOI":"10.1145\/941079.941088"},{"key":"2_CR36","doi-asserted-by":"crossref","unstructured":"Wattenhofer, R., Li, L., Bahl, P., Wang, Y.-M.: Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks. In: Proc. of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) (2001)","DOI":"10.1109\/INFCOM.2001.916634"},{"key":"2_CR37","doi-asserted-by":"crossref","unstructured":"Wattenhofer, R., Zollinger, A.: XTC: A Practical Topology Control Algorithm for Ad-Hoc Networks. In: Proceedings of 4th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN) (2004)","DOI":"10.1109\/IPDPS.2004.1303248"},{"key":"2_CR38","unstructured":"Xue, Y., Li, B., Nahrstedt, K.: A scalable location management scheme in mobile ad-hoc networks. In: IEEE LCN (2001)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30559-0_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T17:32:56Z","timestamp":1635615176000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30559-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241324","9783540305590"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30559-0_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}