{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T18:03:44Z","timestamp":1773079424951,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642148484","type":"print"},{"value":"9783642148491","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T00:00:00Z","timestamp":1289174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T00:00:00Z","timestamp":1289174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-14849-1_3","type":"book-chapter","created":{"date-parts":[[2011,4,27]],"date-time":"2011-04-27T15:47:28Z","timestamp":1303919248000},"page":"59-84","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Maintaining Connectivity in Sensor Networks Using Directional Antennae"],"prefix":"10.1007","author":[{"given":"Evangelos","family":"Kranakis","sequence":"first","affiliation":[]},{"given":"Danny","family":"Krizanc","sequence":"additional","affiliation":[]},{"given":"Oscar","family":"Morales","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,11,8]]},"reference":[{"issue":"3","key":"3_CR1","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.comgeo.2007.09.001","volume":"40","author":"M. Abellanas","year":"2008","unstructured":"M. Abellanas, A. Garc\u00eda, F. Hurtado, J. Tejel, and J. Urrutia. Augmenting the connectivity of geometric graphs. Computational Geometry: Theory and Applications, 40(3):220\u2013230, 2008.","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"3","key":"3_CR2","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s00453-004-1103-4","volume":"40","author":"S. Arora","year":"2004","unstructured":"S. Arora and K. Chang. Approximation Schemes for Degree-Restricted MST and Red\u2013Blue Separation Problems. Algorithmica, 40(3):189\u2013210, 2004.","journal-title":"Algorithmica"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"L. Bao and J. J. Garcia-Luna-Aceves. Transmission scheduling in ad hoc networks with directional antennas. Proceedings of the 8th Annual International Conference on Mobile Computing and Networking, pages 48\u201358, Atlanta, Georgia, USA, 2002.","DOI":"10.1145\/570645.570652"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"B. Bhattacharya, Y Hu, E. Kranakis, D. Krizanc, and Q. Shi. Sensor Network Connectivity with Multiple Directional Antennae of a Given Angular Sum. 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2009), May 25\u201329, Rome, Italy, 2009.","DOI":"10.1109\/IPDPS.2009.5160982"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"I. Caragiannis, C. Kaklamanis, E. Kranakis, D. Krizanc, and A. Wiese. Communication in Wireless Networks with Directional Antennae. In proceedings of 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201908), June 14\u201316, pages 344\u2013351, Munich, Germany, 2008.","DOI":"10.1145\/1378533.1378592"},{"issue":"2","key":"3_CR6","first-page":"177","volume":"32","author":"T. M. Chan","year":"2004","unstructured":"T. M. Chan. Euclidean bounded-degree spanning tree ratios. Discrete and Computational Geometry, 32(2):177\u2013194, 2004.","journal-title":"Discrete and Computational Geometry"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"E. Ch\u00e1vez, S. Dobrev, E. Kranakis, J. Opatrny, L. Stacho, and J. Urrutia. Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges. In LATIN 2006, LNCS, Vol. 3887, pages 286\u2013297, 2006.","DOI":"10.1007\/11682462_29"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"J. Cheriyan, A. Seb\u00f6, and Z. Szigeti. An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs. In Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, Vol. 1412, pages 126\u2013136. Springer, Berlin, 1998.","DOI":"10.1007\/3-540-69346-7_10"},{"key":"#cr-split#-3_CR9.1","doi-asserted-by":"crossref","unstructured":"J. Czyzowicz, S. Dobrev, H. Gonzalez-Aguilar, R. Kralovic, E. Kranakis, J. Opatrny, L. Stacho, and J. Urrutia. Local 7-Coloring for Planar Subgraphs of Unit Disk Graphs. In Theory and Applications of Models of Computation: 5th International Conference, TAMC 2008, Xi'an, China, April 25-29, 2008","DOI":"10.1007\/978-3-540-79228-4_15"},{"key":"#cr-split#-3_CR9.2","unstructured":"Proceedings, vol. 4978, pages 170-181. Springer, Berlin, 2008."},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"S. Dobrev, E. Kranakis, D. Krizanc, O. Morales, J. Opatrny, and L. Stacho. Strong connectivity in sensor networks with given number of directional antennae of bounded angle, 2010. COCOA 2010, to appear.","DOI":"10.1007\/978-3-642-17461-2_6"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Q. Dong and Y. Bejerano. Building Robust Nomadic Wireless Mesh Networks Using Directional Antennas. In IEEE INFOCOM 2008. The 27th Conference on Computer Communications, pages 1624\u20131632, Phoenix, AZ, USA, 2008.","DOI":"10.1109\/INFOCOM.2008.223"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0095-8956(74)90091-4","volume":"3","author":"H. Fleischner","year":"1974","unstructured":"H. Fleischner. The square of every two-connected graph is Hamiltonian. Journal of Combinatorial Theory, 3:29\u201334, 1974.","journal-title":"Journal of Combinatorial Theory"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"A. Francke and M. Hoffmann. The Euclidean degree-4 minimum spanning tree problem is NP-hard. In Proceedings of the 25th Annual Symposium on Computational Geometry, pages 179\u2013188. ACM, New York, NY, 2009.","DOI":"10.1145\/1542362.1542399"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"T. Fukunaga. Graph Orientations with Set Connectivity Requirements. In Proceedings of the 20th International Symposium on Algorithms and Computation, pages 265\u2013274. Springer, LNCS, Honolulu, Hawaii, 2009.","DOI":"10.1007\/978-3-642-10631-6_28"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson, and R. E. Tarjan. The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5:704, 1976.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"3_CR16","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1109\/18.825799","volume":"46","author":"P. Gupta","year":"2000","unstructured":"P. Gupta and P. R. Kumar. The capacity of wireless networks. Information Theory, IEEE Transactions On, 46(2):388\u2013404, 2000.","journal-title":"Information Theory, IEEE Transactions On"},{"key":"3_CR17","unstructured":"L. Hu and D. Evans. Using directional antennas to prevent wormhole attacks. In Network and Distributed System Security Symposium (NDSS), pages 131\u2013141. Internet Society, San Diego, California, USA, 2004."},{"key":"3_CR18","unstructured":"H. Imai, K. Kobara, and K. Morozov. On the possibility of key agreement using variable directional antenna. In Proc. of 1st Joint Workshop on Information Security,(Korea). IEICE, 2006."},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A. Itai","year":"1982","unstructured":"A. Itai, C.H. Papadimitriou, and J.L. Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11:676, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR20","volume-title":"Graph Coloring Problems","author":"T. R. Jensen","year":"1996","unstructured":"T. R. Jensen and B. Toft. Graph Coloring Problems. Wiley-Interscience, New York, NY, 1996."},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"S. Khuller, B. Raghavachari, and N. Young. Low degree spanning trees of small weight. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, page 421. ACM, Montreal, Quebec, Canada, 1994.","DOI":"10.1145\/195058.195212"},{"issue":"4","key":"3_CR22","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/BF01294129","volume":"14","author":"S. Khuller","year":"1995","unstructured":"S. Khuller, B. Raghavachari, and N. Young. Balancing minimum spanning trees and shortest-path trees. Algorithmica, 14(4):305\u2013321, 1995.","journal-title":"Algorithmica"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"E. Kranakis, D. Krizanc, and J. Urrutia. Coverage and Connectivity in Networks with Directional Sensors. proceedings Euro-Par Conference, Pisa, Italy, August, pages 917\u2013924, Pisa, Italy, 2004.","DOI":"10.1007\/978-3-540-27866-5_122"},{"key":"3_CR24","first-page":"357","volume":"3544","author":"E. Kranakis","year":"2004","unstructured":"E. Kranakis, D. Krizanc, and E. Williams. Directional versus omnidirectional antennas for energy consumption and k-connectivity of networks of sensors. Proceedings of OPODIS, 3544:357\u2013368, 2004.","journal-title":"Proceedings of OPODIS"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"E. Kranakis, O. Morales, and L. Stacho. On orienting planar sensor networks with bounded stretch factor, 2010. Unpublished manuscript.","DOI":"10.1007\/978-3-642-13284-1_18"},{"key":"3_CR26","first-page":"2003","volume":"14","author":"X. Li","year":"2003","unstructured":"X. Li, G. Calinescu, P Wan, and Y. Wang. Localized Delaunay Triangulation with Application in Ad Hoc Wireless Networks. IEEE Transactions on Parallel and Distributed Systems, 14:2003, 2003.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"X. Lu, F. Wicker, P. Lio, and D. Towsley. Security Estimation Model with Directional Antennas. In IEEE Military Communications Conference, 2008. MILCOM 2008, pages 1\u20136, 2008.","DOI":"10.1109\/MILCOM.2008.4753607"},{"issue":"1","key":"3_CR28","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"C. Monma","year":"1992","unstructured":"C. Monma and S. Suri. Transitions in geometric minimum spanning trees. Discrete and Computational Geometry, 8(1):265\u2013293, 1992.","journal-title":"Discrete and Computational Geometry"},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"555","DOI":"10.4153\/CJM-1960-049-6","volume":"12","author":"C. S. J. A. Nash-Williams","year":"1960","unstructured":"C. S. J. A. Nash-Williams. On orientations, connectivity and odd vertex pairings in finite graphs. Canadian Journal of Mathematics, 12:555\u2013567, 1960.","journal-title":"Canadian Journal of Mathematics"},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"V. Navda, A. P. Subramanian, K. Dhanasekaran, A. Timm-Giel, and S. Das. Mobisteer: using steerable beam directional antenna for vehicular network access. In ACM MobiSys, 2007.","DOI":"10.1145\/1247660.1247684"},{"issue":"6","key":"3_CR31","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0167-6377(84)90077-4","volume":"2","author":"R. G. Parker","year":"1984","unstructured":"R. G. Parker and R. L. Rardin. Guaranteed performance heuristics for the bottleneck traveling salesman problem. Operations Research Letters, 2(6):269\u2013272, 1984.","journal-title":"Operations Research Letters"},{"key":"3_CR32","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1155\/JAMDS.2005.107","volume":"2","author":"A. P. Punnen","year":"2005","unstructured":"A. P. Punnen. Minmax strongly connected subgraphs with node penalties. Journal of Applied Mathematics and Decision Sciences, 2:107\u2013111, 2005.","journal-title":"Journal of Applied Mathematics and Decision Sciences"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"R. Ramanathan. On the performance of ad hoc networks with beamforming antennas. Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing, pages 95\u2013105, Long Beach, CA, USA, 2001.","DOI":"10.1145\/501416.501430"},{"issue":"6","key":"3_CR34","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1137\/0218075","volume":"18","author":"D. Rappaport","year":"1989","unstructured":"D. Rappaport. Computing simple circuits from a set of line segments is NP-complete. SIAM Journal on Computing, 18(6):1128\u20131139, 1989.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"3_CR35","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jctb.1997.1750","volume":"70","author":"N. Robertson","year":"1997","unstructured":"N. Robertson, D. Sanders, P. Seymour, and R. Thomas. The four-colour theorem. Journal of Combinatorial Theory Series B, 70(1):2\u201344, 1997.","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"3_CR36","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.endm.2008.06.009","volume":"31","author":"I. Rutter","year":"2008","unstructured":"I. Rutter and A. Wolff. Augmenting the connectivity of planar and geometric graphs. Electronic Notes in Discrete Mathematics, 31:53\u201356, 2008.","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"3_CR37","unstructured":"A. Spyropoulos and C. S. Raghavendra. Energy efficient communications in ad hoc networks using directional antennas. INFOCOM 2002: Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, New York, NY, USA, 2002."},{"key":"3_CR38","unstructured":"A. Spyropoulos and C. S. Raghavendra. Capacity bounds for ad-hoc networks using directional antennas. ICC\u201903: IEEE International Conference on Communications, Anchorage, Alaska, USA, 2003."},{"key":"3_CR39","doi-asserted-by":"crossref","unstructured":"S. Yi, Y. Pei, and S. Kalyanaraman. On the capacity improvement of ad hoc wireless networks using directional antennas. Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing, pages 108\u2013116, Annapolis, Maryland, USA, 2003.","DOI":"10.1145\/778415.778429"},{"issue":"3","key":"3_CR40","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1137\/S0097539702408247","volume":"34","author":"H. Zhang","year":"2005","unstructured":"H. Zhang and X. He. On even triangulations of 2-connected embedded graphs. SIAM Journal on Computing, 34(3):683\u2013696, 2005.","journal-title":"SIAM Journal on Computing"}],"container-title":["Monographs in Theoretical Computer Science. An EATCS Series","Theoretical Aspects of Distributed Computing in Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14849-1_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,18]],"date-time":"2023-02-18T03:51:01Z","timestamp":1676692261000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-14849-1_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,8]]},"ISBN":["9783642148484","9783642148491"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14849-1_3","relation":{},"ISSN":["1431-2654"],"issn-type":[{"value":"1431-2654","type":"print"}],"subject":[],"published":{"date-parts":[[2010,11,8]]},"assertion":[{"value":"8 November 2010","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}