Um Algoritmo Distribuído para Encontrar Conjuntos k-Dominantes em Grafos

Autores

1816
Lucia Draque Penso
520,163
1817
Valmir Carneiro Barbosa
(Orientador)
520,163

Informações:

Publicações do PESC

Título
Um Algoritmo Distribuído para Encontrar Conjuntos k-Dominantes em Grafos
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
15/12/1999
Resumo
PESC: Resumo de Dissertação de Mestrado Resumo da Tese apresentada à COPPE/UFRJ como parte dos requisitos necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)

Um Algoritmo Distribuído para Encontrar Conjuntos k-Dominantes em Grafos

Lucia Draque Penso

Dezembro/1999
Orientador: Valmir Carneiro Barbosa  

 
Programa: Engenharia de Sistemas e Computação

      Esta tese apresenta um algoritmo distribuído rápido para encontrar um conjunto k-dominante pequeno D num grafo G(n,m), onde n é o número de nós de G, m é o número de arestas de G e n > k+1. Um conjunto k-dominante D de G consiste num conjunto de nós tal que para todo nó v de G existe um nó de D que dista no máximo k de v. D é dito um conjunto k-dominante pequeno quando possuir no máximo [n/k+1] nós, que é o melhor limite inferior de tamanho para D no caso geral. O algoritmo é síncrono, sua complexidade de tempo é O(klog*n) e sua complexidade de mensagens é O(nlogklog*n). Conjuntos k-dominantes pequenos possuem aplicações em várias áreas, como no projeto de estruturas de dados distribuídas, na escolha da localização de servidores numa rede, e no roteamento com tabelas esparsas. Finalmente, é interessante observar que o problema de decisão relacionado à busca do menor conjunto k-dominante D num grafo G é um problema NP-Completo.

Abstract
PESC: Master's Degree Abstract Abstract of Thesis presented at COPPE/UFRJ as a partial fulfillment of the requirements for the degree of Master of Science (M.Sc.)

A Distributed Algorithm to Find k-Dominating Sets in Graphs

Lucia Draque Penso

December/1999
Advisor:Valmir Carneiro Barbosa  
Department: Systems Engineering and Computer Science

      This thesis presents a fast distributed algorithm to find a small k-dominating set D in a graph G(n,m), where n is the number of nodes of G, m is the number of edges of G and n > k + 1. A k-dominating set D of G is a set of nodes such that for every node v of G, there exists a node of G whose distance to v is at most k. D is said to be a small k-dominating set if it has at most [n/k+1] nodes, which is the best upper bound for the size of D in general. The algorithm is synchronous, its time complexity is O(klog*n) and its message complexity is O(mlogklog*n). Small k-dominating sets have applications in a number of areas, including the design of distributed data structures, the selection of servers in a network, and routing with sparse tables. Note, finally, that the decision problem related to fiding the smallest k-dominating set of G is NP-Complete.

Arquivo
Topo