{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:44Z","timestamp":1740109304923,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T00:00:00Z","timestamp":1637107200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T00:00:00Z","timestamp":1637107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s00453-021-00889-6","type":"journal-article","created":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T05:03:10Z","timestamp":1637125390000},"page":"150-175","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Bounded-Angle Minimum Spanning Trees"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6396-4494","authenticated-orcid":false,"given":"Ahmad","family":"Biniaz","sequence":"first","affiliation":[]},{"given":"Prosenjit","family":"Bose","sequence":"additional","affiliation":[]},{"given":"Anna","family":"Lubiw","sequence":"additional","affiliation":[]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,17]]},"reference":[{"issue":"3","key":"889_CR1","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.comgeo.2012.07.003","volume":"46","author":"E Ackerman","year":"2013","unstructured":"Ackerman, E., Gelander, T., Pinchasi, R.: Ice-creams and wedge graphs. Comput. Geometry Theory Appl. 46(3), 213\u2013218 (2013)","journal-title":"Comput. Geometry Theory Appl."},{"key":"889_CR2","doi-asserted-by":"crossref","unstructured":"Aichholzer, O., Hackl, T., Hoffmann, M., Huemer, C., P\u00f3r, A., Santos, F., Speckmann, B., Vogtenhuber, B.: Maximizing maximal angles for plane straight-line graphs. Comput. Geometry Theory Appl. Also in WADS\u201907 46(1), 17\u201328 (2013)","DOI":"10.1016\/j.comgeo.2012.03.002"},{"issue":"5","key":"889_CR3","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"889_CR4","doi-asserted-by":"crossref","unstructured":"Aschner, R., Katz, M.\u00a0J.: Bounded-angle spanning tree: modeling networks with angular constraints. Algorithmica. Also in ICALP\u201914 77(2), 349\u2013373 (2017)","DOI":"10.1007\/s00453-015-0076-9"},{"key":"889_CR5","doi-asserted-by":"crossref","unstructured":"Aschner, R., Katz, M.\u00a0J., Morgenstern, G.: Do directional antennas facilitate in reducing interferences? In: Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 201\u2013212 (2012)","DOI":"10.1007\/978-3-642-31155-0_18"},{"issue":"9","key":"889_CR6","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1016\/j.comgeo.2013.06.003","volume":"46","author":"R Aschner","year":"2013","unstructured":"Aschner, R., Katz, M.J., Morgenstern, G.: Symmetric connectivity with directional antennas. Comput. Geometry Theory Appl. 46(9), 1017\u20131026 (2013)","journal-title":"Comput. Geometry Theory Appl."},{"key":"889_CR7","doi-asserted-by":"crossref","unstructured":"Ashur, S., Katz, M.\u00a0J.: A 4-approximation of the $$2\\pi \/3$$-MST. In: Proceedings of the 17th International Symposium on Algorithms and Data Structures (WADS), pages 129\u2013143 (2021)","DOI":"10.1007\/978-3-030-83508-8_10"},{"key":"889_CR8","doi-asserted-by":"crossref","unstructured":"Biniaz, A.: Euclidean bottleneck bounded-degree spanning tree ratios. In ACM-SIAM Symposium on Discrete Algorithms (SODA) (2020)","DOI":"10.1137\/1.9781611975994.50"},{"key":"889_CR9","doi-asserted-by":"crossref","unstructured":"Biniaz, A., Maheshwari, A., Smid, M.: Flip distance to some plane configurations. Comput. Geometry Theory Appl. 81, 12\u201321 (2019). Also in SWAT\u201918","DOI":"10.1016\/j.comgeo.2019.01.008"},{"key":"889_CR10","doi-asserted-by":"crossref","unstructured":"Bose, P., Carmi, P., Damian, M., Flatland, R.\u00a0Y., Katz, M.\u00a0J., Maheshwari, A.: Switching to directional antennas with constant increase in radius and hop distance. Algorithmica 69(2), 397\u2013409 (2014) Also in WADS\u201911","DOI":"10.1007\/s00453-012-9739-y"},{"key":"889_CR11","doi-asserted-by":"crossref","unstructured":"Bose, P., Guibas, L.\u00a0J., Lubiw, A., Overmars, M.\u00a0H., Souvaine, D.\u00a0L., Urrutia, J.: The floodlight problem. Int. J. Comput. Geometry Appl. 7(1\/2), 153\u2013163 (1997). Also in CCCG\u201993","DOI":"10.1142\/S0218195997000090"},{"issue":"3","key":"889_CR12","doi-asserted-by":"publisher","first-page":"1527","DOI":"10.1137\/100819540","volume":"27","author":"G C\u0103linescu","year":"2013","unstructured":"C\u0103linescu, G.: Approximate min-power strong connectivity. SIAM J. Discret. Math. 27(3), 1527\u20131543 (2013)","journal-title":"SIAM J. Discret. Math."},{"key":"889_CR13","doi-asserted-by":"crossref","unstructured":"C\u0103linescu, G., Mandoiu, I.\u00a0I., Zelikovsky, A.: Symmetric connectivity with minimum power consumption in radio networks. In Proceedings of the 2$${}^{\\text{nd}}$$IFIP International Conference on Theoretical Computer Science (TCS), pages 119\u2013130, (2002)","DOI":"10.1007\/978-0-387-35608-2_11"},{"issue":"1","key":"889_CR14","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/0020-0190(78)90030-3","volume":"7","author":"PM Camerini","year":"1978","unstructured":"Camerini, P.M.: The min-max spanning tree problem and some extensions. Inf. Process. Lett. 7(1), 10\u201314 (1978)","journal-title":"Inf. Process. Lett."},{"key":"889_CR15","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Kaklamanis, C., Kranakis, E., Krizanc, D., Wiese, A.: Communication in wireless networks with directional antennas. In Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 344\u2013351, (2008)","DOI":"10.1145\/1378533.1378592"},{"issue":"9","key":"889_CR16","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1016\/j.comgeo.2011.05.003","volume":"44","author":"P Carmi","year":"2011","unstructured":"Carmi, P., Katz, M.J., Lotker, Z., Ros\u00e9n, A.: Connectivity guarantees for wireless networks with directional antennas. Comput. Geometry Theory Appl. 44(9), 477\u2013485 (2011)","journal-title":"Comput. Geometry Theory Appl."},{"key":"889_CR17","doi-asserted-by":"crossref","unstructured":"Chan, T.\u00a0M.: Euclidean bounded-degree spanning tree ratios. Discret. Comput. Geometry 32(2),177\u2013194 (2004). Also in SoCG\u201903","DOI":"10.1007\/s00454-004-1117-3"},{"key":"889_CR18","doi-asserted-by":"crossref","unstructured":"Damian, M., Flatland, R.\u00a0Y.: Spanning properties of graphs induced by directional antennas. Discret. Math. Algorithm. Appl. 5(3) (2013)","DOI":"10.1142\/S1793830913500080"},{"key":"889_CR19","doi-asserted-by":"crossref","unstructured":"Dobrev, S., Kranakis, E., Krizanc, D., Opatrny, J., Ponce, O.\u00a0M., Stacho, L.: Strong connectivity in sensor networks with given number of directional antennae of bounded angle. Discret. Math. Algorith. Appl. 4(3) (2012). Also in COCOA\u201910","DOI":"10.1142\/S1793830912500383"},{"key":"889_CR20","doi-asserted-by":"crossref","unstructured":"Dobrev, S., Kranakis, E., Ponce, O.\u00a0M., Plz\u00edk, M.: Robust sensor range for constructing strongly connected spanning digraphs in UDGs. In Proceedings of the 7th International Computer Science Symposium in Russia (CSR), pages 112\u2013124 (2012)","DOI":"10.1007\/978-3-642-30642-6_12"},{"key":"889_CR21","doi-asserted-by":"crossref","unstructured":"Dumitrescu, A., Pach, J., T\u00f3th, G.: Drawing Hamiltonian cycles with no large angles. Electron. J. Combin. 19(2), P31 (2012). Also in GD\u201994","DOI":"10.37236\/2356"},{"key":"889_CR22","doi-asserted-by":"crossref","unstructured":"Fekete, S.\u00a0P., Khuller, S., Klemmstein, M., Raghavachari, B., Young, N.\u00a0E.: A network-flow technique for finding low-weight bounded-degree spanning trees. J. Algorithm. 24(2), 310\u2013324 (1997). Also in IPCO 1996","DOI":"10.1006\/jagm.1997.0862"},{"key":"889_CR23","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0925-7721(96)00012-0","volume":"8","author":"SP Fekete","year":"1997","unstructured":"Fekete, S.P., Woeginger, G.J.: Angle-restricted tours in the plane. Comput. Geometry Theory Appl. 8, 195\u2013218 (1997)","journal-title":"Comput. Geometry Theory Appl."},{"issue":"1","key":"889_CR24","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.tcs.2008.03.003","volume":"402","author":"MM Halld\u00f3rsson","year":"2008","unstructured":"Halld\u00f3rsson, M.M., Tokuyama, T.: Minimizing interference of a wireless ad-hoc network in a plane. Theor. Comput. Sci. 402(1), 29\u201342 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"889_CR25","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1016\/j.dam.2008.03.037","volume":"157","author":"R Jothi","year":"2009","unstructured":"Jothi, R., Raghavachari, B.: Degree-bounded minimum spanning trees. Discret. Appl. Math. 157(5), 960\u2013970 (2009)","journal-title":"Discret. Appl. Math."},{"key":"889_CR26","unstructured":"Katz, M.\u00a0J.: Personal communication"},{"key":"889_CR27","doi-asserted-by":"crossref","unstructured":"Khuller, S., Raghavachari, B., Young, N.\u00a0E.: Low-degree spanning trees of small weight. SIAM J. Comput. 25(2), 355\u2013368 (1996). Also in STOC\u201994","DOI":"10.1137\/S0097539794264585"},{"issue":"1\u20132","key":"889_CR28","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/S0304-3975(98)00223-0","volume":"243","author":"LM Kirousis","year":"2000","unstructured":"Kirousis, L.M., Kranakis, E., Krizanc, D., Pelc, A.: Power consumption in packet radio networks. Theor. Comput. Sci. 243(1\u20132), 289\u2013305 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"889_CR29","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.tcs.2015.04.035","volume":"590","author":"E Kranakis","year":"2015","unstructured":"Kranakis, E., MacQuarrie, F., Ponce, O.M.: Connectivity and stretch factor trade-offs in wireless sensor networks with directional antennae. Theor. Comput. Sci. 590, 55\u201372 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"889_CR30","doi-asserted-by":"crossref","unstructured":"Monma, C.\u00a0L., Suri, S.: Transitions in geometric minimum spanning trees. Discret. Comput. Geometry 8, 265\u2013293 (1992). Also in SoCG\u201991","DOI":"10.1007\/BF02293049"},{"key":"889_CR31","doi-asserted-by":"crossref","unstructured":"Tran, T., An, M.\u00a0K., Huynh, D.\u00a0T.: Antenna orientation and range assignment algorithms in directional WSNs. IEEE\/ACM Trans. Network. 25(6), 3368\u20133381 (2017). Also in INFOCOM\u201916","DOI":"10.1109\/TNET.2017.2743008"},{"key":"889_CR32","unstructured":"van Leeuwen, J., Schoone, A.\u00a0A.: Untangling a travelling salesman tour in the plane. In Proceedings of the 7th Conference Graph Theoretic Concepts in Computer Science$$(WG)$$, pages 87\u201398 (1981)"},{"key":"889_CR33","unstructured":"van Nijnatten, F.: Range assignment with directional antennas. Master\u2019s thesis, Technische Universiteit Eindhoven (2008)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00889-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00889-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00889-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T14:06:50Z","timestamp":1643033210000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00889-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,17]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["889"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00889-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,11,17]]},"assertion":[{"value":"29 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}