6 research outputs found
Abstract
No full textWe give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most 2; 1 colours, and maximal matchings can be computed within O(log n +) deterministic rounds, where is the maximum degree of the network. We also show how to nd maximal independent sets and ( + 1)-vertex colourings within O(log n + 2) deterministic rounds. All hidden constants are very small and the algorithms are very simple. Key words: distributed computing, sparse networks, maximal independent set, maximal matching, vertex colouring, edge colouring.
Cuts and Disjoint Paths in the Valley-Free Path Model ∗
No full textIn the valley-free path model, a path in a given directed graph is valid if it consists of a sequence of forward edges followed by a sequence of backward edges. This model is motivated by routing policies of autonomous systems in the Internet. We give a 2-approximation algorithm for the problem of computing a maximum number of edge- or vertex-disjoint valid paths between two given vertices s and t, and we show that no better approximation ratio is possible unless P = NP. Furthermore, we give a 2-approximation algorithm for the problem of computing a minimum vertex cut that separates s and t with respect to all valid paths and prove that the problem is APX-hard. The corresponding problem for edge cuts is shown to be polynomial-time solvable. For the multiway variant of the cut problem, we give a 4-approximation algorithm. We present additional results for acyclic graphs.
Blue Pleiades, a new solution for device discovery and scatternet formation in multihop Bluetooth networks, WINET
No full text1 Introduction The Bluetooth (BT) technology, as described in the Specifications of the Bluetooth System Version 1.1 is one of the most promising enabling technologies for pervasive and ubiquitous computing. In this paper we provide basic results to the fundamental problems of device discovery and scatternet formation, i.e. on how Bluetooth nodes can become aware of their neighbors (device discovery), can partition themselves into groups, called piconets, and finally on how such groups can be joined together to form a connected multi-hop ad hoc network, the so-called scatternet. To describe our contribution we first review the two main unsolved problems in this context. A more thorough discussion of the existing literature is deferred to the next section
Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons
No full textRumor Spreading in Random Evolving Graphs
No full textInternational audienceIn this paper, we aim at analyzing the classical information spreading push protocol in dynamic networks. We consider the edge-Markovian evolving graph model which captures natural temporal dependencies between the structure of the network at time t, and the one at time t + 1. Precisely, a non-edge appears with probability p, while an existing edge dies with probability q. In order to fit with real-world traces, we mostly concentrate our study on the case where p=Ω(1n) and q is constant. We prove that, in this realistic scenario, the push protocol does perform well, completing information spreading in O(logn) time steps, w.h.p., even when the network is, w.h.p., disconnected at every time step (e.g., when p≪lognn). The bound is tight. We also address other ranges of parameters p and q (e.g., p + q = 1 with arbitrary p and q, and p=Θ(1n) with arbitrary q). Although they do not precisely fit with the measures performed on real-world traces, they can be of independent interest for other settings. The results in these cases confirm the positive impact of dynamism
