Indexed by:
Abstract:
When the edge between two nodes is not measured, is there any hint to know the edge property, and will the inferred edge property be useful? To answer these questions, this paper uniformly defines the properties of unmeasurable edges in generic graphs. For an unmeasurable edge $(i,j)$ , it is called rangeable if its length is unique in any realization of the graph, rigid if the number of its possible lengths is finite, and flexible if it has infinite possible lengths. The rangeable edge can provide deterministic hidden knowledge as if the edge is measured. A condition for an unmeasured edge being rangeable in 2D space is firstly proposed, based on which a centralized identification algorithm (DRE) is designed. However, the centralized rangeable edge identification has the overhead of global information collection. Therefore distributed condition and algorithm to identify rangeable edges are further investigated. We prove that an unmeasurable edge $(i,j)$ is rangeable if there are at least two Disjoint Minimally Rigid Branches (DMRBs) between $i$ and $j$ . The unmeasurable edge $(i,j)$ is rigid and flexible when the number of DMRB is one and zero, respectively. A distributed Branching and Blacklisting (BB) algorithm is proposed to find DMRBs, so that rangeable edges are identified distributively. Then, the applications of rangeable, rigid, and flexible edges are discussed. Experimental evaluations show that the centralized and distributed algorithms can identify a rich set of unmeasurable but rangeable edges in distance graphs, even more than the number of directly measured edges. Moreover, BB has a similar identification performance as the centralized DRE algorithm and outperforms existing distributed unmeasurable edge inference algorithms significantly. IEEE
Keyword:
Reprint Author's Address:
Email:
Source :
ACM Transactions on Networking
ISSN: 1063-6692
Year: 2024
Issue: 3
Volume: 32
Page: 1-15
3 . 7 0 0
JCR@2022
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2
Affiliated Colleges: