{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T17:00:29Z","timestamp":1726851629989},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61972404, 12071478"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Public Computing Cloud, Renmin University of China"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2023,11,30]]},"abstract":"\n Partitioning the\n Maximal Redundant Rigid Components (MRRC)<\/jats:italic>\n and\n Maximal Global Rigid Components (MGRC)<\/jats:italic>\n in generic 2D graphs are critical problem for network structure analysis, network localizability detection, and localization algorithm design. This article presents efficient algorithms to partition MRRCs and MGRCs and develops an open-sourced toolbox, GPART, for these algorithms to be conveniently used by the society. We firstly propose conditions and an efficient algorithm to merge the over-constrained regions to form the maximal redundant rigid components (MRRC). The detected MRRCs are proved to be maximal and all the MRRCs are guaranteed to be detected. The time to merge the over-constrained regions is linear to the number of nodes in the over-constrained components. To detect MGRCs, the critical problem is to decompose 3-connected components in each MRRC. We exploit SPQR-tree based method and design a local optimization algorithm, called MGRC_acce to prune the unnecessary decomposition operations so that the SPQR-tree functions can be called much less number of times. We prove the MGRCs can be detected inside MRRCs using at most\n O(mn<\/jats:italic>\n ) time. Then a GPART toolbox is developed and extensively tested in graphs of different densities. We show the proposed MRRC and MGRC detection algorithms are valid and MGRC_acce greatly outperforms the direct SPQR-tree based decomposition algorithm. GPART is outsourced at\n https:\/\/github.com\/inlab-group\/gpart<\/jats:ext-link>\n .\n <\/jats:p>","DOI":"10.1145\/3594668","type":"journal-article","created":{"date-parts":[[2023,4,29]],"date-time":"2023-04-29T11:13:47Z","timestamp":1682766827000},"page":"1-26","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["GPART: Partitioning Maximal Redundant Rigid and Maximal Global Rigid Components in Generic Distance Graphs"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-8372-3412","authenticated-orcid":false,"given":"Yu","family":"Zhang","sequence":"first","affiliation":[{"name":"Renmin University of China"}]},{"ORCID":"http:\/\/orcid.org\/0009-0002-7370-2866","authenticated-orcid":false,"given":"Qinhan","family":"Wei","sequence":"additional","affiliation":[{"name":"Renmin University of China"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-4197-2258","authenticated-orcid":false,"given":"Yongcai","family":"Wang","sequence":"additional","affiliation":[{"name":"Renmin University of China"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-7947-7826","authenticated-orcid":false,"given":"Haodi","family":"Ping","sequence":"additional","affiliation":[{"name":"Renmin University of China"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-7748-5427","authenticated-orcid":false,"given":"Deying","family":"Li","sequence":"additional","affiliation":[{"name":"Renmin University of China"}]}],"member":"320","published-online":{"date-parts":[[2023,6,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.09.002"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1353\/ajm.0.0132"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44541-2_8"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221008"},{"key":"e_1_3_2_6_2","article-title":"Finding the triconnected components of a graph","author":"Hopcroft J. E.","year":"1972","unstructured":"J. E. Hopcroft and R. E. Tarjan. 1972. Finding the triconnected components of a graph. Technical Report TR 140, Dept. of Computer Science, Cornell Univ.","journal-title":"Technical Report TR 140, Dept. of Computer Science, Cornell Univ."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"e_1_3_2_8_2","volume-title":"Levico Conference Notes","volume":"4","author":"Jackson Bill","year":"2007","unstructured":"Bill Jackson. 2007. Notes on the rigidity of graphs. In Levico Conference Notes, Vol. 4."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.11.002"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1997.5809"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01534980"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-010-9324-2"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031502"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCCN49398.2020.9209620"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3547143"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","unstructured":"H. Ping Y. Wang D. Li and T. Sun. 2022. Flipping free conditions and their application in sparse network localization. IEEE Transactions on Mobile Computing 21 3 (2022) 986\u20131003.","DOI":"10.1109\/TMC.2020.3015480"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03089-0_23"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.11.022"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.07.104"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2866597"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1971.10"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2018.2864374"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2017.2748563"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462060"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2009.5062166"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2018.2873015"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3594668","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T10:26:33Z","timestamp":1686306393000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3594668"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,9]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,11,30]]}},"alternative-id":["10.1145\/3594668"],"URL":"http:\/\/dx.doi.org\/10.1145\/3594668","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"value":"1550-4859","type":"print"},{"value":"1550-4867","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,9]]},"assertion":[{"value":"2022-09-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-13","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
