{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:36:52Z","timestamp":1740141412517,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,1,23]],"date-time":"2024-01-23T00:00:00Z","timestamp":1705968000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,23]],"date-time":"2024-01-23T00:00:00Z","timestamp":1705968000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100019923","name":"DEVCOM Army Research Laboratory","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100019923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Intell Robot Syst"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A key function of mobile networks is the ability to dynamically reshape itself to any desired geometry. Lacking absolute position awareness, agents often rely on distance-limited inter-agent spatial measurements to maintain state awareness. Methods of formation control must therefore ensure a minimal level of persistent pairwise measurement feedback throughout transition, giving rise to the classic connectivity maintenance problem. To address this problem, we propose a method of structure-preserving assignment, matching agents to desired positions such that persistent global connectivity is naturally and automatically satisfied under smooth transition. Compared to other approaches, this complementary technique reduces reliance on aggressive or costly mid-flight formation control protocols. The technique is shown to scale and even improve with network size.<\/jats:p>","DOI":"10.1007\/s10846-024-02048-9","type":"journal-article","created":{"date-parts":[[2024,1,23]],"date-time":"2024-01-23T08:02:37Z","timestamp":1705996957000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Connectivity Maintenance through Unlabeled Spanning Tree Matching"],"prefix":"10.1007","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4851-4823","authenticated-orcid":false,"given":"Moshe","family":"Hamaoui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,23]]},"reference":[{"key":"2048_CR1","doi-asserted-by":"publisher","unstructured":"Oh, K.K., Park, M.C., Ahn, H.S.: A survey of multi-agent formation control. Automatica 53, 424\u2013440 (2015). https:\/\/doi.org\/10.1016\/j.automatica.2014.10.022https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0005109814004038","DOI":"10.1016\/j.automatica.2014.10.022"},{"key":"2048_CR2","doi-asserted-by":"crossref","unstructured":"Mesbahi, M., Egerstedt, M.: Graph theoretic methods in multiagent networks. Princeton series in applied mathematics (Princeton University Press, Princeton, 2010), pp xix, 403","DOI":"10.1515\/9781400835355"},{"issue":"1","key":"2048_CR3","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1109\/TCNS.2014.2367363","volume":"2","author":"Z Kan","year":"2015","unstructured":"Kan, Z., Navaravong, L., Shea, J.M., Pasiliao, E.L., Dixon, W.E.: Graph matching-based formation reconfiguration of networked agents with connectivity maintenance. IEEE Trans. Control Netw Syst. 2(1), 24\u201335 (2015). https:\/\/doi.org\/10.1109\/TCNS.2014.2367363","journal-title":"IEEE Trans. Control Netw Syst."},{"issue":"4","key":"2048_CR4","doi-asserted-by":"publisher","first-page":"2149","DOI":"10.1109\/TCYB.2020.3000264","volume":"52","author":"J Fu","year":"2022","unstructured":"Fu, J., Wen, G., Yu, X., Wu, Z.G.: Distributed formation navigation of constrained second-order multiagent systems with collision avoidance and connectivity maintenance. IEEE Trans. Cybernet. 52(4), 2149\u20132162 (2022). https:\/\/doi.org\/10.1109\/TCYB.2020.3000264","journal-title":"IEEE Trans. Cybernet."},{"issue":"9","key":"2048_CR5","doi-asserted-by":"publisher","first-page":"1525","DOI":"10.1109\/JPROC.2011.2157884","volume":"99","author":"MM Zavlanos","year":"2011","unstructured":"Zavlanos, M.M., Egerstedt, M.B., Pappas, G.J.: Graph-theoretic connectivity control of mobile robot networks. Proceedings of the IEEE 99(9), 1525\u20131540 (2011). https:\/\/doi.org\/10.1109\/JPROC.2011.2157884","journal-title":"Proceedings of the IEEE"},{"key":"2048_CR6","doi-asserted-by":"publisher","unstructured":"Li, A., Wang, L., Pierpaoli, P., Egerstedt, M.: in 2018 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) (2018), pp 3723\u20133729. https:\/\/doi.org\/10.1109\/IROS.2018.8594302","DOI":"10.1109\/IROS.2018.8594302"},{"key":"2048_CR7","doi-asserted-by":"publisher","unstructured":"Luo, W., Sycara, K.: in 2019 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) (2019), pp 7370\u20137377. https:\/\/doi.org\/10.1109\/IROS40897.2019.8968058","DOI":"10.1109\/IROS40897.2019.8968058"},{"key":"2048_CR8","doi-asserted-by":"crossref","unstructured":"Zahroof, R., Liu, J., Zhou, L., Kumar, V.: Multi-robot localization and target tracking with connectivity maintenance and collision avoidance (2022). arXiv:2210.03300","DOI":"10.23919\/ACC55779.2023.10155978"},{"issue":"4","key":"2048_CR9","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1109\/TRO.2007.900638","volume":"23","author":"M Ji","year":"2007","unstructured":"Ji, M., Egerstedt, M.: Distributed coordination control of multiagent systems while preserving connectedness. IEEE Trans. Robot. 23(4), 693\u2013703 (2007). https:\/\/doi.org\/10.1109\/TRO.2007.900638","journal-title":"IEEE Trans. Robot."},{"key":"2048_CR10","doi-asserted-by":"publisher","unstructured":"Ren, W., Beard, R.W.: Distributed consensus in multi-vehicle cooperative control (Springer, 2008). https:\/\/doi.org\/10.1007\/978-1-84800-015-5","DOI":"10.1007\/978-1-84800-015-5"},{"key":"2048_CR11","doi-asserted-by":"crossref","unstructured":"Ren, W., Cao, Y.: Distributed coordination of multi-agent networks: emergent problems, models, and issues (Springer Science & Business Media, 2011)","DOI":"10.1007\/978-0-85729-169-1"},{"key":"2048_CR12","doi-asserted-by":"publisher","unstructured":"Lewis, F.L., Zhang, H., Hengster-Movric, K., Das, A.: Cooperative control of multi-agent systems: optimal and adaptive design approaches (Springer Science & Business Media, 2013). https:\/\/doi.org\/10.1007\/978-1-4471-5574-4","DOI":"10.1007\/978-1-4471-5574-4"},{"issue":"1\u20132","key":"2048_CR13","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The hungarian method for the assignment problem. Naval Research Logistics Quarterly 2(1\u20132), 83\u201397 (1955). https:\/\/doi.org\/10.1002\/nav.3800020109","journal-title":"Naval Research Logistics Quarterly"},{"issue":"8","key":"2048_CR14","doi-asserted-by":"publisher","first-page":"3210","DOI":"10.1109\/TAC.2018.2885491","volume":"64","author":"K Sakurama","year":"2019","unstructured":"Sakurama, K., Azuma, S.I., Sugie, T.: Multiagent coordination via distributed pattern matching. IEEE Trans. Automatic Control 64(8), 3210\u20133225 (2019). https:\/\/doi.org\/10.1109\/TAC.2018.2885491","journal-title":"IEEE Trans. Automatic Control"},{"key":"2048_CR15","doi-asserted-by":"publisher","unstructured":"Raymond, J.W., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J. Comput.-Aided Molecular Design 16(7), 521\u2013533 (2002). https:\/\/doi.org\/10.1023\/a:1021271615909","DOI":"10.1023\/a:1021271615909"},{"issue":"2","key":"2048_CR16","first-page":"213","volume":"77","author":"E Duesbury","year":"2017","unstructured":"Duesbury, E., Holliday, J.D., Willett, P.: Maximum common subgraph isomorphism algorithms. MATCH Commun. Mathematical Comput. Chemistry 77(2), 213\u2013232 (2017)","journal-title":"MATCH Commun. Mathematical Comput. Chemistry"},{"issue":"7","key":"2048_CR17","doi-asserted-by":"publisher","first-page":"S13","DOI":"10.1186\/1471-2105-14-s7-s13","volume":"14","author":"V Bonnici","year":"2013","unstructured":"Bonnici, V., Giugno, R., Pulvirenti, A., Shasha, D., Ferro, A.: A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinfor. 14(7), S13 (2013). https:\/\/doi.org\/10.1186\/1471-2105-14-s7-s13","journal-title":"BMC Bioinfor."},{"key":"2048_CR18","doi-asserted-by":"crossref","unstructured":"Conte, D., Foggia, P., Sansone, C., Vento, M.: How and why pattern recognition and computer vision applications use graphs (Springer, 2007), pp 85\u2013135","DOI":"10.1007\/978-3-540-68020-8_4"},{"key":"2048_CR19","doi-asserted-by":"crossref","unstructured":"Crussell, J., Gibler, C., Chen, H.: in European Symposium on Research in Computer Security (Springer, 2012), pp 37\u201354","DOI":"10.1007\/978-3-642-33167-1_3"},{"issue":"1","key":"2048_CR20","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"JR Ullmann","year":"1976","unstructured":"Ullmann, J.R.: An algorithm for subgraph isomorphism. J. ACM 23(1), 31\u201342 (1976). https:\/\/doi.org\/10.1145\/321921.321925","journal-title":"J. ACM"},{"issue":"10","key":"2048_CR21","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/tpami.2004.75","volume":"26","author":"LP Cordella","year":"2004","unstructured":"Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367\u201372 (2004). https:\/\/doi.org\/10.1109\/tpami.2004.75","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"2048_CR22","doi-asserted-by":"publisher","unstructured":"Junttila, T., Kaski, P.: Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs (SIAM, 2007), pp 135\u2013149. https:\/\/doi.org\/10.1137\/1.9781611972870.13","DOI":"10.1137\/1.9781611972870.13"},{"key":"2048_CR23","doi-asserted-by":"publisher","unstructured":"Solnon, C.: Alldifferent-based filtering for subgraph isomorphism. Artif. Intell. 174(12\u201313), 850\u2013864 (2010). https:\/\/doi.org\/10.1016\/j.artint.2010.05.002","DOI":"10.1016\/j.artint.2010.05.002"},{"key":"2048_CR24","doi-asserted-by":"publisher","unstructured":"Ullmann, J.R.: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. J. Exper. Algorithmics 15, 1.1 (2010). https:\/\/doi.org\/10.1145\/1671970.1921702","DOI":"10.1145\/1671970.1921702"},{"issue":"1","key":"2048_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.7155\/jgaa.00139","volume":"11","author":"D Conte","year":"2007","unstructured":"Conte, D., Foggia, P., Vento, M.: Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs. J. Graph Algorithms Appl. 11(1), 99\u2013143 (2007)","journal-title":"J. Graph Algorithms Appl."},{"key":"2048_CR26","doi-asserted-by":"publisher","unstructured":"Lee, J., Han, W.S., Kasperovics, R., Lee, J.H.: An in-depth comparison of subgraph isomorphism algorithms in graph databases. Proc. VLDB Endow. 6(2), 133\u2013144 (2012). https:\/\/doi.org\/10.14778\/2535568.2448946","DOI":"10.14778\/2535568.2448946"},{"key":"2048_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-018-9759-9","author":"A Dutta","year":"2018","unstructured":"Dutta, A., Dasgupta, P., Nelson, C.: Distributed configuration formation with modular robots using (sub)graph isomorphism-based approach. Autonomous Robots (2018). https:\/\/doi.org\/10.1007\/s10514-018-9759-9","journal-title":"Autonomous Robots"},{"key":"2048_CR28","unstructured":"Kann, V.: On the approximability of np-complete optimization problems. Ph.D. thesis, Royal Institute of Technology Stockholm (1992)"},{"issue":"4","key":"2048_CR29","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/bf02575586","volume":"9","author":"G Levi","year":"1973","unstructured":"Levi, G.: A note on the derivation of maximal common subgraphs of two directed or undirected graphs. CALCOLO 9(4), 341 (1973). https:\/\/doi.org\/10.1007\/bf02575586","journal-title":"CALCOLO"},{"key":"2048_CR30","unstructured":"Datta S.: Graph density. https:\/\/www.baeldung.com\/cs\/graph-density (2022). Accessed on: October 19, 2023"},{"key":"2048_CR31","doi-asserted-by":"crossref","unstructured":"Zwillinger, D.: CRC standard mathematical tables and formulae (Chapman and Hall\/CRC, 2002)","DOI":"10.1201\/9781420035346"},{"key":"2048_CR32","unstructured":"Recuero, P.: Toward an enumeration of unlabeled trees (2017)"},{"key":"2048_CR33","unstructured":"Wolfram Research, Inc. Mathematica, Version 13.1. Champaign, IL, 2022"},{"key":"2048_CR34","doi-asserted-by":"crossref","unstructured":"Wallenius, K.T.: Biased sampling; the noncentral hypergeometric probability distribution. Report, STANFORD UNIV CA APPLIED MATHEMATICS AND STATISTICS LABS (1963)","DOI":"10.21236\/AD0426243"},{"issue":"4","key":"2048_CR35","doi-asserted-by":"publisher","first-page":"795","DOI":"10.2307\/3212535","volume":"13","author":"J Chesson","year":"1976","unstructured":"Chesson, J.: A non-central multivariate hypergeometric distribution arising from biased sampling with application to selective predation. J. Appl. Probability 13(4), 795\u2013797 (1976)","journal-title":"J. Appl. Probability"},{"issue":"2","key":"2048_CR36","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1080\/03610910701790269","volume":"37","author":"A Fog","year":"2008","unstructured":"Fog, A.: Calculation methods for wallenius\u2019 noncentral hypergeometric distribution. Commun. Stat. - Simulation Comput. 37(2), 258\u2013273 (2008). https:\/\/doi.org\/10.1080\/03610910701790269","journal-title":"Commun. Stat. - Simulation Comput."},{"key":"2048_CR37","unstructured":"Kalinka, A.T.: The probability of drawing intersections: extending the hypergeometric distribution (2013). arXiv:1305.0717"},{"key":"2048_CR38","unstructured":"The on-line encyclopedia of integer sequences (2023). https:\/\/oeis.org\/A000055"},{"key":"2048_CR39","unstructured":"Borg, I., Groenen, P.J.: Modern multidimensional scaling: Theory and applications (Springer Science & Business Media, 2005)"}],"container-title":["Journal of Intelligent &amp; Robotic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10846-024-02048-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10846-024-02048-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10846-024-02048-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T02:17:28Z","timestamp":1711937848000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10846-024-02048-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,23]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["2048"],"URL":"https:\/\/doi.org\/10.1007\/s10846-024-02048-9","relation":{},"ISSN":["0921-0296","1573-0409"],"issn-type":[{"type":"print","value":"0921-0296"},{"type":"electronic","value":"1573-0409"}],"subject":[],"published":{"date-parts":[[2024,1,23]]},"assertion":[{"value":"20 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"Not applicable","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}],"article-number":"15"}}