Catálogo de publicaciones - libros

We study the complexity of distributed protocols for the classical information dissemination problem of . We consider the model of , one of the main models used to study properties of sensor and ad-hoc networks, where points are randomly placed in a unit square and two points are connected by an edge/link if they are at at most a certain fixed distance from each other. To study communication in the network, we consider the  −  model of communication. We examine various scenarios depending on the local knowledge of each node in the networks, and show that in many settings distributed gossiping in asymptotically optimal time is possible, where is the diameter of the network and thus a trivial lower bound for any communication.

Gossiping is an important problem in Radio Networks that has been well studied, leading to many important results. Due to strong resouce limitations of sensor nodes, previous solutions are frequently not feasible in Sensor Networks. In this paper, we study the gossiping problem in the restrictive context of Sensor Networks. By exploiting the geometry of sensor node distributions, we present reduced, optimal running time of ( + ) for an algorithm that completes gossiping with high probability in a Sensor Network of unknown topology and adversarial wake-up, where is the diameter and the maximum degree of the network. Given that an algorithm for gossiping also solves the broadcast problem, our result proves that the classic lower bound of [16] can be broken if nodes are allowed to do preprocessing.

We show that if a minimal-time solution exists for a fundamental distributed computation primitive, synchronizing arbitrary undirected networks of finite-state processors, then there must exist an “extraordinarily fast” algorithm in the RAM model of computation for exactly determining the diameter of an arbitrary unweighted undirected graph with edges. The proof is constructive.

At present we know eight variations of the firing squad synchronization problems whose solutions are known but whose minimal-time solutions are not known. Our result essentially completes the program outlined in [3] to show that it is highly unlikely for there to exist minimal-time solutions for these variations.

We consider a generalization of the well-known domination problem on graphs. The () capacitated domination problem with demand constraints is to find a dominating set of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demand of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in is unbounded. The demand constraint specifies that the demand of each vertex in is met by the capacities of vertices in dominating it. In this paper, we study the capacitated domination problem on trees. We present a linear time algorithm for the unsplittable demand model, and a pseudo-polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP-complete (even for its integer version) and provide a -approximation algorithm. We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs.

The class of graphs where the size of a minimum vertex cover equals that of a maximum matching is known as König-Egerváry graphs. These graphs have been studied extensively from a graph theoretic point of view. In this paper, we introduce and study the algorithmic complexity of finding maximum König-Egerváry subgraphs of a given graph. More specifically, we look at the problem of finding a minimum number of vertices or edges to delete to make the resulting graph König-Egerváry. We show that both these versions are NP-complete and study their complexity from the points of view of approximation and parameterized complexity. En route, we point out an interesting connection between the vertex deletion version and the problem where one is interested in the parameterized complexity of the problem when parameterized by the ‘additional number of vertices’ needed beyond the matching size. This connection is of independent interest and could be useful in establishing the parameterized complexity of problem.

An edge coloring of a multigraph is nearly equitable if, among the edges incident to each vertex, the numbers of edges colored with any two colors differ by at most two. It has been proved that this problem can be solved in (/) time, where and are the numbers of edges and given colors, respectively. In this paper, we present a recursive algorithm that runs in time, where  is the number of vertices. This algorithm improves the best-known worst-case time complexity. When  = (1), the time complexity of all known algorithms is (), which implies that this time complexity remains to be the best for more than twenty years since 1982 when Hilton and de Werra gave a constructive proof for the existence of a nearly equitable edge coloring for any graph. Our result is the first that improves this time complexity when / grows to infinity; e.g.,  =  for an arbitrary constant > 1. We also propose a very simple randomized algorithm that runs in time with probability at least 1 − 1/ for any constant  > 1, whose worst-case time complexity is (/).

We consider the (MCEI) in a graph  = (,) with edge weight () ≥ 0,  ∈ . We are given a vertex  ∈  designated as a sink, an edge capacity > 0, and a source set  ⊆  with demand () ∈ [0,],  ∈ . For any edge  ∈ , we are allowed to install an integer number () of copies of . The MCEI asks to send demand () from each source  ∈  along a single path to the sink . A set of such paths can pass through a single copy of an edge in as long as the total demand along the paths does not exceed the edge capacity . The objective is to find a set of paths of that minimizes the installing cost ∑ () (). In this paper, we propose a -approximation algorithm to the MCEI, where is any approximation ratio achievable for the .

Given a graph , the edge-disjoint cycle packing problem is to find the largest set of cycles of which no two share an edge. For undirected graphs, the best known approximation algorithm has ratio [14,15]. In fact, they proved the same upper bound for the integrality gap of this problem by presenting a simple greedy algorithm. Here we show that this is almost best possible. By modifying integrality gap and hardness results for the edge-disjoint paths problem [1,9], we show that the undirected edge-disjoint cycle packing problem has an integrality gap of and furthermore it is quasi-NP-hard to approximate the edge-disjoint cycle problem within ratio of for any constant > 0. The same results hold for the problem of packing vertex-disjoint cycles.

In many applications, the properties of an object being modeled are stored as labels on vertices or edges of a graph. In this paper, we consider succinct representation of labeled graphs. Our main results are the succinct representations of labeled and multi-labeled graphs (we consider vertex labeled planar triangulations, as well as edge labeled planar graphs and the more general -page graphs) to support various label queries efficiently. The additional space cost to store the labels is essentially the information-theoretic minimum. As far as we know, our representations are the first succinct representations of labeled graphs. We also have two preliminary results to achieve the main results. First, we design a succinct representation of unlabeled planar triangulations to support the rank/select of edges in ccw (counter clockwise) order in addition to the other operations supported in previous work. Second, we design a succinct representation for a -page graph when is large to support various navigational operations more efficiently. In particular, we can test the adjacency of two vertices in time, while previous work uses () time (10; 14).

There is a large literature devoted to the problem of finding an optimal (min-cost) prefix-free code with an unequal letter-cost encoding alphabet of size. While there is no known polynomial time algorithm for optimally solving it, there are many good heuristics that all provide additive errors to optimal. The additive error in these algorithms usually depends linearly upon the size of the largest encoding letter.

This paper was motivated by the problem of finding optimal codes when the encoding alphabet is infinite. Because the largest letter cost is infinite, the previous analyses could give infinite error bounds. We provide a new algorithm that works with infinite encoding alphabets. When restricted to the finite alphabet case, our algorithm often provides better error bounds than the best previous ones known.