Search

Summary: Fault‐tolerance and self‐organization are critical properties in modern distributed systems. Self‐stabilization is a class of fault‐tolerant distributed algorithms which has the ability to recover from any kind and any finite number of transient faults and topology changes. In this article, we propose a self‐stabilizing distributed algorithm for the 1‐MIS problem under the unfair central daemon assuming the distance‐3 model. Here, in the distance‐3 model, each process can refer to the values of local variables of processes within three hops. Intuitively speaking, the 1‐MIS problem is a variant of the maximal independent set (MIS) problem with improved local optimizations. The time complexity (convergence time) of our algorithm is O(n)$$ O(n) $$ steps and the space complexity is O(logn)$$ O\left(\log n\right) $$ bits, where n$$ n $$ is the number of processes. Finally, we extend the notion of 1‐MIS to p$$ p $$‐MIS for each nonnegative integer p$$ p $$, and compare the set sizes of p$$ p $$‐MIS (p=0,1,2,...$$ p=0,1,2,\dots $$) and the maximum independent set. [ABSTRACT FROM AUTHOR]

Let Γ ${\rm{\Gamma }}$ be the graph whose vertices are the chambers of the finite projective 3‐space PG(3,q) $\text{PG}(3,q)$, with two vertices being adjacent if and only if the corresponding chambers are in general position. We show that a maximal independent set of vertices of Γ ${\rm{\Gamma }}$ contains q4+3q3+4q2+3q+1 ${q}^{4}+3{q}^{3}+4{q}^{2}+3q+1$, or 3q3+5q2+3q+1 $3{q}^{3}+5{q}^{2}+3q+1$, or at most 3q3+4q2+3q+2 $3{q}^{3}+4{q}^{2}+3q+2$ elements. For q≥4 $q\ge 4$ the structure of the largest maximal independent sets is described. For q≥7 $q\ge 7$ the structure of the maximal independent sets of the three largest cardinalities is described. Using the cardinality of the second largest maximal independent sets, we show that the chromatic number of Γ ${\rm{\Gamma }}$ is q2+q ${q}^{2}+q$. [ABSTRACT FROM AUTHOR]

This study devises self-stabilizing algorithms that leverage the expression distance-2 paradigm to compute (i) a maximal distance-2 independent set, wherein selected nodes maintain a separation exceeding two edges, ensuring non-adjacency; and (ii) a minimal dominating set, wherein each external node has at least one node as a neighbor in the dominating set. The efficacy and convergence of the algorithms are established through rigorous proofs within the framework of the expression model. Extensive simulation tests validate the algorithms' proficiency in selecting a minimal subset of nodes across expansive network topologies. These algorithms find practical applications in network operations, particularly in ad hoc and wireless sensor networks for the selection of cluster heads that facilitate critical services. Moreover, the self-stabilizing property of the algorithms guarantees the robust reconfiguration of cluster heads post-failure, thereby preserving network functionality amidst disruptions. [ABSTRACT FROM AUTHOR]

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Δ + log* n) communication rounds; here, n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: These problems cannot be solved in o(log* n) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that any algorithm that finds a maximal matching or maximal independent set with probability at least 1 - 1/n requires Ω(min{Δ, log logn/ log log logn}) rounds in the LOCAL model of distributed computing. As a corollary, it follows that any deterministic algorithm that finds a maximal matching or maximal independent set requires Ω(min{Δ, logn/ log logn}) rounds; this is an improvement over prior lower bounds also as a function of n. [ABSTRACT FROM AUTHOR]

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices, while the weight of a set of vertices is the sum of their weights. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space, denoted WCW(G). In what follows, all weights are real. Let B be a complete bipartite induced subgraph of G on vertex sets of bipartition B X and B Y . Then B is generating if there exists an independent set S such that S ∪ B X and S ∪ B Y are both maximal independent sets of G. Generating subgraphs play an important role in finding WCW(G). In the restricted case that a generating subgraph B is isomorphic to K 1 , 1 , its unique edge is called a relating edge. Deciding whether an input graph G is well-covered is co-NP-complete. Therefore finding WCW(G) is co-NP-hard. Deciding whether an edge is relating is NP-complete. Therefore, deciding whether a subgraph is generating is NP-complete as well. This article deals with graphs G such that Δ (G) = | V (G) | - k for some k ∈ N . We prove that for this family recognizing well-covered graphs is a polynomial problem, while finding WCW(G) is co-NP-hard. To the best of our knowledge, this is the first family of graphs in the literature known to have these properties. For this set of graphs, recognizing relating edges and generating subgraphs is NP-complete. The article also deals with connected graphs for which δ (G) = k or δ (G) ≥ k - 1 k | V (G) | . For these families of graphs recognizing well-covered graphs is co-NP-complete, while recognizing relating edges is NP-complete. [ABSTRACT FROM AUTHOR]

We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph G = (V , E) is the average over the times at which the nodes V of G finish their computation and commit to their outputs. We study the node-averaged complexity for some of the central distributed symmetry breaking problems and provide the following results (among others). As our main result, we show that the randomized node-averaged complexity of computing a maximal independent set (MIS) in n-node graphs of maximum degree Δ is at least Ω (min { log Δ log log Δ , log n log log n }) . This bound is obtained by a novel adaptation of the well-known lower bound by Kuhn, Moscibroda, and Wattenhofer [JACM'16]. As a side result, we obtain that the worst-case randomized round complexity for computing an MIS in trees is also Ω (min { log Δ log log Δ , log n log log n }) —this essentially answers open problem 11.15 in the book by Barenboim and Elkin and resolves the complexity of MIS on trees up to an O (log log n) factor. We also show that, perhaps surprisingly, a minimal relaxation of MIS, which is the same as (2, 1)-ruling set, to the (2, 2)-ruling set problem drops the randomized node-averaged complexity to O(1). For maximal matching, we show that while the randomized node-averaged complexity is Ω (min { log Δ log log Δ , log n log log n }) , the randomized edge-averaged complexity is O(1). Further, we show that the deterministic edge-averaged complexity of maximal matching is O (log 2 Δ + log ∗ n) and the deterministic node-averaged complexity of maximal matching is O (log 3 Δ + log ∗ n) . Finally, we consider the problem of computing a sinkless orientation of a graph. The deterministic worst-case complexity of the problem is known to be Θ (log n) , even on bounded-degree graphs. We show that the problem can be solved deterministically with node-averaged complexity O (log ∗ n) , while keeping the worst-case complexity in O (log n) . [ABSTRACT FROM AUTHOR]

For a given finite commutative ring R with 1 ≠ 0 , one may associate a graph which is called the total graph of R. This graph has R as the vertex set and its two distinct vertices x and y are adjacent exactly whenever x + y is a zero-divisor of R. In this paper, we give necessary and sufficient conditions for two classes of total graphs to be Cohen–Macaulay. [ABSTRACT FROM AUTHOR]

An independent dominating set of a graph, also known as a maximal independent set, is a set S of pairwise non-adjacent vertices such that every vertex not in S is adjacent to some vertex in S. We prove that for Δ = 4 or Δ ≥ 6 , every connected n -vertex graph of maximum degree at most Δ has an independent dominating set of size at most (1 − Δ ⌊ Δ 2 / 4 ⌋ + Δ) (n − 1) + 1. In addition, we characterize all connected graphs having the equality and we show that other connected graphs have an independent dominating set of size at most (1 − Δ ⌊ Δ 2 / 4 ⌋ + Δ) n. [ABSTRACT FROM AUTHOR]

A Maximal Independent Set (MIS) is an inclusion maximal set of pairwise non-adjacent vertices. The computation of an MIS is one of the core problems in distributed computing. In this article, we introduce and analyze a finite-state distributed randomized algorithm for computing a Maximal Independent Set (MIS) on arbitrary undirected graphs. Our algorithm is self-stabilizing (reaches a correct output on any initial configuration) and can be implemented on systems with very scarce conditions. We analyze the convergence time of the proposed algorithm, showing that in many cases the algorithm converges in logarithmic time with high probability. [ABSTRACT FROM AUTHOR]

Self-stabilizing protocols enable distributed systems to recover correct behavior starting from any arbitrary configuration. In particular, when processors communicate by message passing and the communication links are unbounded, fake messages may be placed in communication links by an adversary. When the number of such fake messages is unknown, self-stabilization may require huge resources: • generic solutions (a.k.a. data link protocols) require unbounded resources, which makes them unrealistic to deploy, • specific solutions (e.g. , census or tree construction) require O (n log ⁡ n) or O (Δ log ⁡ n) bits of memory per node, where n denotes the network size and Δ its maximum degree, which may prevent scalability. We investigate the possibility of resource-efficient self-stabilizing protocols in this context. Specifically, we present self-stabilizing protocols for (Δ + 1) -coloring and maximal independent set construction in any n -node graph, under the asynchronous message-passing model. The problems of (Δ + 1) -coloring and maximal independent set construction are widely regarded as benchmark problems for evaluating local algorithms. Our protocols offer many desirable features. They are deterministic, converge in O (k Δ n 2 log ⁡ n) message exchanges, where k is the (unknown) initial number of (possibly corrupted) messages in a communication link. They use messages of O (log ⁡ log ⁡ n + log ⁡ Δ) bits with a memory of O (Δ log ⁡ Δ + log ⁡ log ⁡ n) bits at each node. The resource consumption of our protocols is thus almost oblivious to the number of nodes, enabling scalability. Moreover, a striking property of our protocols is that the nodes do not need to know the number, or any bound on the number of messages initially present in each communication link of the initial (potentially corrupted) network configuration. This permits our protocols to handle any future network with unknown message capacity communication links. A key building block of our coloring and maximal independent set schemes is an algorithm to obtain an acyclic orientation of graph edges, that is of independent interest, and can serve as a useful tool for solving other tasks in this challenging setting. [ABSTRACT FROM AUTHOR]

Self-stabilization is a promising paradigm for designing highly adaptive distributed systems. However, it cannot be realized when the communication between processes is unreliable with some constant probability. To circumvent such impossibility, this paper adopts the concept of loose-stabilization for the first time, which is a practical alternative of self-stabilization, and proposes three systematic approaches to realize loose-stabilization in the atomic-state model with probabilistically erroneous communications , namely, the redundant-state approach, the step-up approach, and the repetition approach. Further, we apply these approaches to design three corresponding loosely-stabilizing algorithms for the maximal independent set problem. • Self-stabilization solutions are precluded for most of non-trivial problems in probabilistic error models. • Loose-stabilization is a relaxed variant of self-stabilization and practically equivalent to it. • Loose-stabilization can circumvent the impossibilities of self-stabilization in probabilistic error models. • Adopt the concept of loose-stabilization in the atomic-state model for the first time. • Three loose-stabilizing algorithms for maximal independent set problem. [ABSTRACT FROM AUTHOR]

An independent dominating set of a graph is a vertex subset that is both dominating and independent set in the graph, i.e., a maximal independent set. Also, the independent domination polynomial is an ordinary generating function for the number of independent dominating sets in the graph. In this paper, we examine independent domination polynomials of zero-divisor graphs of the ring Z n where n ∈ { 2 p , p 2 , p α , p q , p 2 q , p q r } and their roots. Finally, we prove the log-concavity and unimodality of their independent domination polynomials. [ABSTRACT FROM AUTHOR]

For any n and l , we completely describe trees with the maximum and minimum numbers of maximal independent sets among all n -vertex trees with l leaves. [ABSTRACT FROM AUTHOR]

Given a graph G = (V,E), an (α, β)-ruling set is a subset S ⊆ V such that the distance between any two vertices in S is at least α, and the distance between any vertex in V and the closest vertex in S is at most \beta. We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a (2, β)-ruling set (and hence also any (α, β)-ruling set with α > 2) in the LOCAL model of distributed computing, we show the following, where n denotes the number of vertices, γ the maximum degree, and c is some universal constant independent of n and γ: (a) Any deterministic algorithm requires \Omega (min\{ logγ β log logγ, logγ n\}) rounds for all β \leq c \c. min\{ √{} logγ log logγ, logγ n\}. By optimizing γ, this implies a deterministic lower bound of \Omega (√{} log n β log log n) for all β \leq c 3 √{} log n log log n. (b) Any randomized algorithm requires \Omega (min\{ logγ β log logγ, logγ log n\}) rounds for all β \leq c \c. min\{ √{} logγ log logγ, logγ log n\}. By optimizing γ, this implies a randomized lower bound of \Omega (√{} log log n β log log log n) for all β \leq c 3 √{} log log n log log log n. For β > 1, this improves on the previously best lower bound of \Omega (log\ast n) rounds that follows from the 30-yearold bounds of Linial [SIAM J. Comput., 21(1992), pp. 193--201] and Naor [SIAM J. Discrete Math., 4(1991), pp. 409--412] (resp., \Omega (1) rounds if β \in \omega (log\ast n)). For β = 1, i.e., for the problem of computing a maximal independent set (which is nothing else than a (2, 1)-ruling set), our results improve on the previously best lower bound of \Omega (log\ast n) on trees, as our bounds already hold on trees. For the maximal independent set on general graphs, a deterministic lower bound of \Omega (min\{ γ, logγ n\}) and a randomized lower bound of \Omega (min\{ γ, logγ log n\}) were already known due to Balliu et al. [Proceedings of FOCS, 2019, pp. 481--497]. [ABSTRACT FROM AUTHOR]

A complete description of trees with maximal possible number of maximum independent sets among all n-vertex trees with exactly l leaves is obtained. For all values of the parameters n and l the extremal tree is unique and is the result of merging the endpoints of l simple paths. [ABSTRACT FROM AUTHOR]

The Massively Parallel Computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a newgraph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP'86], we obtain O(log Δ + log logn)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set withO(ne) space on each machine for any constant e > 0. These algorithms also run inO(log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log² Δ) rounds by Censor-Hillel et al. [DISC'17]. [ABSTRACT FROM AUTHOR]

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w well-covered if all maximal independent sets are of the same weight. For every graph G , the set of weight functions w such that G is w -well-covered is a vector space, denoted as WCW(G). Deciding whether an input graph G is well-covered is co-NP-complete. Therefore, finding WCW(G) is co-NP-hard. A generating subgraph of a graph G is an induced complete bipartite subgraph B of G on vertex sets of bipartition B X and B Y , such that each of S ∪ B X and S ∪ B Y is a maximal independent set of G , for some independent set S. If B is generating, then w (B X) = w (B Y) for every weight function w ∈ W C W (G). Therefore, generating subgraphs play an important role in finding WCW(G). The decision problem whether a subgraph of an input graph is generating is known to be NP-complete. In this article we prove NP- completeness of the problem for graphs without cycles of length 3 and 5, and for bipartite graphs with girth at least 6. On the other hand, we supply polynomial algorithms for recognizing generating subgraphs and finding WCW(G), when the input graph is bipartite without cycles of length 6. We also present a polynomial algorithm which finds WCW(G) when G does not contain cycles of lengths 3, 4, 5, and 7. [ABSTRACT FROM AUTHOR]

We introduce vector weighted Stirling numbers, which are a generalization of ordinary Stirling numbers and restricted Stirling numbers. Some relations between vector weighted Stirling numbers and ordinary Stirling numbers and some of their applications are stated. Moreover, as an application of vector weighted Stirling numbers of the second kind in graph theory, we compute the number of maximal independent sets of different sizes in k-intersection graphs. [ABSTRACT FROM AUTHOR]

We propose a dynamic distributed resource allocation algorithm for wireless networks, where the resources allocated to adjacent nodes (vertices) must be different and the topology of the network (graph) may change. Time is divided into rounds. In each round, a maximal independent set (MIS) is found, and the vertices in the MIS will use the resource in the next round. Therefore, the resource reuse equals the expected value of sizes of MISs, and we present two lower bounds for it. The number of messages transmitted by each vertex included/excluded in the MIS is one/zero, and messages are 1-bit. Therefore, the independence number of the graph is an upper bound for the number of bits transmitted in a round. [ABSTRACT FROM AUTHOR]

Interference in femtocells due to neighboring femtocells and macrocells is a major issue of two-tier networks. Handover should be made to reduce interference, if and only if, when resources are available. Otherwise, it will further degrade network performance. Resource management should be made in an efficient manner that will not cause interference between macrocells and neighboring femtocells. Since distance between macro base station (MBS) and femto access point (FAP) is short, therefore, it is very hard to sustain low handover probability when macro user moves from MBS to FAP. We proposed handover algorithm for uplink co-channel interference mitigation that will make handover decision on the basis of time-to-stay and signal to interference plus noise ratio thresholds along with efficient resource management mechanism to reduce number of handovers and also resolve interference problem. [ABSTRACT FROM AUTHOR]

We consider the problem of maintaining a maximal independent set in a dynamic graph subject to edge insertions and deletions. Recently, Assadi et al. (at STOC'18) showed that a maximal independent set can be maintained in sublinear (in the dynamically changing number of edges) amortized update time. In this article, we significantly improve the update time for uniformly sparse graphs. Specifically, for graphs with arboricity a, the amortized update time of our algorithm is O(a² · log² n), where n is the number of vertices. For low arboricity graphs, which include, for example, minor-free graphs and some classes of "real-world" graphs, our update time is polylogarithmic. Our update time improves the result of Assadi et al. for all graphs with arboricity bounded by m3/8-, for any constant > 0. This covers much of the range of possible values for arboricity, as the arboricity of a general graph cannot exceedm1/2. [ABSTRACT FROM AUTHOR]

For any n, in the set of n-vertex trees such that any two leaves have no common adjacent vertex, we describe the trees with the smallest number of maximal independent sets. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Signal Processing is the property of Journal of Signal Processing and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low independence. A series of papers, beginning with work by Luby (1988), showed that in many cases these techniques can be combined to give deterministic parallel (NC) algorithms for a variety of combinatorial optimization problems, with low time- and processor-complexity. We extend and generalize a technique of Luby for efficiently handling bilinear objective functions. One noteworthy application is an NC algorithm for maximal independent set. On a graph G with m edges and n vertices, this takes O~(log2n) time and (m+n)no(1) processors, nearly matching the best randomized parallel algorithms. Other applications include reduced processor counts for algorithms of Berger (SIAM J Comput 26:1188-1207, 1997) for maximum acyclic subgraph and Gale-Berlekamp switching games. This bilinear factorization also gives better algorithms for problems involving discrepancy. An important application of this is to automata-fooling probability spaces, which are the basis of a notable derandomization technique of Sivakumar (In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp 619-626, 2002). Our method leads to large reduction in processor complexity for a number of derandomization algorithms based on automata-fooling, including set discrepancy and the Johnson-Lindenstrauss Lemma. [ABSTRACT FROM AUTHOR]

Highlights • We propose a maximal independent set algorithm for wireless sensor networks. • The proposed algorithm is fully distributed and self-stabilizing. • The upper bound of the move count is max {3 n − 6 , 2 n − 1 } (n is the node count) and 1.3 moves per node in the average case for random graphs. • We provide theoretical analysis for proof of correctness and average move count. • The proposed algorithm is compared with the previous work through extensive testbed experiments and simulations. Abstract Maximal independent set (MIS) is a very important structure that provides data aggregation, topology control and routing for wireless sensor networks (WSNs). Energy-efficient and fault-tolerant construction of MIS on WSNs is one of the vital tasks. A distributed sensor network is self-stabilizing if it can initially start at any state and regain a legal state in a finite time without any external intervention. Self-stabilization is a considerable method to provide fault tolerance in WSNs. This paper presents a distributed self-stabilizing MIS algorithm which is an improved version of Turau's algorithm under a fully distributed scheduler for WSNs. The proposed algorithm is theoretically analyzed and evaluated with its counterparts. The proposed algorithm is compared with the other studies through testbed experiments on IRIS nodes and simulations on TOSSIM environment. It is shown that the proposed algorithm outperforms other algorithms in terms of move count and energy consumption. [ABSTRACT FROM AUTHOR]

We present a short inductive proof of Brooks' Theorem. [ABSTRACT FROM AUTHOR]

A clutter (or antichain or Sperner family) \(L\) is a pair \((V,E)\), where \(V\) is a finite set and \(E\) is a family of subsets of \(V\) none of which is a subset of another. Usually, the elements of \(V\) are called vertices of \(L\), and the elements of \(E\) are called edges of \(L\). A subset \(s_e\) of an edge \(e\) of a clutter is called recognizing for \(e\), if \(s_e\) is not a subset of another edge. The hardness of an edge \(e\) of a clutter is the ratio of the size of \(e\)'s smallest recognizing subset to the size of \(e\). The hardness of a clutter is the maximum hardness of its edges. We study the hardness of clutters arising from independent sets and matchings of graphs.