3 results
Now showing1 - 3 of 3
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , A O(m) self-stabilizing algorithm for maximal triangle partition of general fraphs(World Scientific Publishing (WSPC), 2017-06-21); ; ; The triangle partition problem is a generalization of the well-known graph matching problem consisting of finding the maximum number of independent edges in a given graph, i.e., edges with no common node. Triangle partition instead aims to find the maximum number of disjoint triangles. The triangle partition problem is known to be NP-complete. Thus, in this paper, the focus is on the local maximization variant, called maximal triangle partition (MTP). Thus, paper presents a new self-stabilizing algorithm for MTP that converges in O(m) moves under the unfair distributed daemon.Publicationtype: Journal Article111 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , A self-stabilizing algorithm for edge monitoring in wireless sensor networksSelf-monitoring is a simple and effective mechanism for surveilling wireless sensor networks, especially to cope against faulty or compromised nodes. A node v can monitor the communication over a link e if both end-nodes of e are neighbors of v. Finding a set of monitoring nodes satisfying all monitoring constraints is called the edge-monitoring problem. The minimum edge-monitoring problem is known to be NP-complete. In this paper, we present a novel self-stabilizing algorithm for computing a minimal edge-monitoring set under the unfair distributed scheduler. For sparse networks the time complexity of this new algorithm is much lower than the currently best known algorithm.Publicationtype: Journal Article118 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , A self-stabilizing algorithm for maximal p-star decomposition of general graphsA p-star is a complete bipartite graph K1,p with one center node and p leaf nodes. In this paper we propose the first distributed self-stabilizing algorithm for graph decomposition into p-stars. For a graph G and an integer p ≥ 1, this decomposition provides disjoint components of G where each component forms a p-star. We prove convergence and correctness of the algorithm under an unfair distributed daemon. The stabilization time is 2[n/p+1] + 2 rounds.Publicationtype: Conference Paper75