This paper is devoted to study the combinatorial properties of Local Minimum Spanning Trees (LMSTs), a geometric structure that is attracting increasing research interest in the wireless sensor networks community. Namely, we study which topologies are allowed for a sensor network that uses, for supporting connectivity, a local minimum spanning tree approach. First, we refine the current definition of LMST realizability, focusing on the role of the power of transmission (i.e., of the radius of the covered area). Second, we show simple planar, connected, and triangle-free graphs with maximum degree 3 that cannot be represented as an LMST. Third, we present several families of graphs that can be represented as LMSTs. Then, we show a relationship between planar graphs and their representability as LMSTs based on homeomorphism. Finally, we show that the general problem of determining whether a graph is LMST representable is NP-hard.
On the Topologies of Local Minimum Spanning Trees
GRILLI, LUCA;LIOTTA, Giuseppe;
2006
Abstract
This paper is devoted to study the combinatorial properties of Local Minimum Spanning Trees (LMSTs), a geometric structure that is attracting increasing research interest in the wireless sensor networks community. Namely, we study which topologies are allowed for a sensor network that uses, for supporting connectivity, a local minimum spanning tree approach. First, we refine the current definition of LMST realizability, focusing on the role of the power of transmission (i.e., of the radius of the covered area). Second, we show simple planar, connected, and triangle-free graphs with maximum degree 3 that cannot be represented as an LMST. Third, we present several families of graphs that can be represented as LMSTs. Then, we show a relationship between planar graphs and their representability as LMSTs based on homeomorphism. Finally, we show that the general problem of determining whether a graph is LMST representable is NP-hard.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
