{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T09:14:51Z","timestamp":1649063691650},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2003,4]]},"abstract":"<jats:p> Mobile Backbone Wireless Networks (MBWN) [10] are wireless networks in which the base stations are mobile. Our strategy is the following: mobile nodes are dynamically grouped into clusters of bounded radius. In the very large wireless networks we deal with we deal with, several hundreds of clusters may be generated. Clustering makes use of a two dimensional Euclidean version of the Antipole Tree data structure [5]. This very effective structure was originally designed for finite sets of points in an arbitrary metric space to support efficient range searching. It requires only a linear number of pair-wise distance calculations among nodes. Mobile Base Stations occupy an approximate centroid of the clusters and are moved according to a fast practical bipartite matching algorithm which tries to minimize both total and maximum distance. We show that the best known computational geometry algorithms [1] become infeasible for our application when a high number of mobile base stations is required. On the other hand our proposed 8% average error solution requires O (k log k) running time instead of the approximatively O (k<jats:sup>2<\/jats:sup>) exact algorithm [1]. Communication among nodes is realized by a Clusterhead Gateway Switching Routing (CGSR) protocol [15] where the mobile base stations are organized in a suitable network. Other efficient clustering algorithms [11, 17] may be used instead of the Antipole Tree. However the nice hierarchical structure of the Antipole Tree makes it applicable to other types of mobile wireless (Ad-Hoc) and wired networks but this will be subject of future work. <\/jats:p>","DOI":"10.1142\/s0129054103001698","type":"journal-article","created":{"date-parts":[[2003,6,19]],"date-time":"2003-06-19T08:43:20Z","timestamp":1056012200000},"page":"223-236","source":"Crossref","is-referenced-by-count":2,"title":["FAST CLUSTERING AND MINIMUM WEIGHT MATCHING ALGORITHMS FOR VERY LARGE MOBILE BACKBONE WIRELESS NETWORKS"],"prefix":"10.1142","volume":"14","author":[{"given":"A.","family":"FERRO","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica e Informatica, Universit\u00e0 degli Studi di Catania, Viale A. Doria, 6 Catania, 95125, Italy"}]},{"given":"G.","family":"PIGOLA","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, Universit\u00e0 degli Studi di Catania, Viale A. Doria, 6 Catania, 95125, Italy"}]},{"given":"A.","family":"PULVIRENTI","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, Universit\u00e0 degli Studi di Catania, Viale A. Doria, 6 Catania, 95125, Italy"}]},{"given":"D.","family":"SHASHA","sequence":"additional","affiliation":[{"name":"Courant Institute of Mathematical Science, New York University, 251 Mercer Street New York, NY 10012, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","author":"Agarwal P. K.","journal-title":"SIAM Journal on Computing"},{"key":"rf2","volume-title":"Advances in Discrete and Computational Geometry","author":"Agarwal P.","year":"1998"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90065-0"},{"key":"rf4","volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","year":"1998"},{"key":"rf6","series-title":"Wiley-Interscience Series In Discrete Mathematics and Optimization","volume-title":"Combinatorial Optimization","author":"Cook W. J.","year":"1998"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0016-8"},{"key":"rf12","unstructured":"M.\u00a0Junger and W.\u00a0Pulleyblank, Jahrbuck Uberblicke Mathematik (Vieweg, Brunschweig Wiesbaden, 1993)\u00a0pp. 1\u201324."},{"key":"rf13","first-page":"63","volume":"32","author":"Mitchell J. S. B.","journal-title":"Internat. Journal Computional Geometry and Applications"},{"key":"rf14","volume-title":"Computational Geometry: An Introduction","author":"Preparata F. P.","year":"1995"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1109\/98.760423"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054103001698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:39:16Z","timestamp":1565138356000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103001698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":11,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,4]]}},"alternative-id":["10.1142\/S0129054103001698"],"URL":"https:\/\/doi.org\/10.1142\/s0129054103001698","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}