China
Africa
Explore chapters and articles related to this topic
Dynamic Processes on Complex Networks
Published in Ervin Sejdić, Tiago H. Falk, Signal Processing and Machine Learning for Biomedical Big Data, 2018
In regime III, the topology-dependent process favors minimizing the number of infected edges (i.e., edges where both end nodes are infected), whereas the topology-independent process favors maximizing the number of infected agents. In other words, these processes favor isolated infected nodes. The solution space of the MPCP is related to the graph theoretic concept of independent sets. An independent set is a subset of nodes such that the induced subgraph is composed entirely of isolated nodes. The maximum independent set is the largest possible independent set for a given graph [42]. The maximum independent set is also the largest maximal independent set (i.e., an independent set that is not a subset of any other independent set).
Sensor Networking Software and Architectures
Published in John R. Vacca, Handbook of Sensor Networking, 2015
In summary, the investigated problem in this chapter is distinguished from all the prior works in three aspects. First, most of the current literature investigates the DAT construction problem under the DNM, whereas our work is suitable for both DNM and PNM. Second, the load-balance factor is not considered when constructing a DAT in most of the aforementioned works. Third, the DAT construction problem is our major concern, whereas the prior works focus on the aggregation scheduling problem. Therefore, in this chapter, we explore the DAT construction problem under the PNM considering balancing the traffic load among all the nodes in a DAT. To be specific, in this chapter, we construct a LBDAT under the PNM in three phases. We first investigate how to construct a load-balanced maximal independent set (LBMIS). A maximal independent set (MIS) can be defined formally as follows: given a graph G=(V,E), an independent set (IS) is a subset ⊆V such that for any two vertex v1,v2∈D, they are not adjacent, that is, v1,v2∉E. An IS is called an MIS if we add one more arbitrary node to this subset; the new subset will not be an IS anymore. After obtaining an LBMIS, we attempt to find a minimum-sized set of nodes called LBMIS connector set C to make this LBMIS M connected, which is called the connected MIS (CMIS) problem. Finally, we seek a load-balanced parent node assignment.
Distributed maximal independent set computation driven by finite-state dynamics
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
Eric Goles, Laura Leal, Pedro Montealegre, Ivan Rapaport, Martín Ríos-Wilson
A set of nodes S is called an independent set if the graph induced by it has no edges. An inclusion-maximal independent set is simply called maximal independent set. The cardinality of an independent set of maximal cardinality is denoted , and is called the independence number of G. The problem of computing is NP-Hard. The range of its value goes from 1 for the complete graph, to n−1 for the case of the star graph. There are a number of combinatorial lower bounds for with respect to some graph parameters. In this article, we make use of the following simple result.