Autores

4701
163,2082
4702
163,2082

Informações:

Publicações do PESC

Título
Senso de Direção Cordal em Sistemas Distribuídos
Linha de pesquisa
Arquitetura e Sistemas Operacionais
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
10/9/2004
Resumo

Senso de direção é uma propriedade de grafos rotulados na qual a rotulação das arestas segue um esquema global consistente. Esta propriedade é conhecida por reduzir consideravelmente a complexidade de diversos problemas distribuídos. Neste trabalho, estudamos uma instância particular de senso de direção denominada senso de direção cordal (SDC). Em especial, caracterizamos a classe de grafos cúbicos que admitem SDC minimal (com o menor número possível de rótulos). Generalizamos vários resultados para a classe dos grafos regulares. Demonstramos que a classe dos grafos regulares que admitem SDC minimal é equivalente à classe dos grafos circulantes, apresentando uma forma eficiente (polinomial) de reconhecimento desta classe quando o grau do grafo é fixo. Analisamos outra propriedade, denominada cobertura dupla por ciclos (CDC), e descrevemos um método construtivo para geração de grafos cúbicos que admitem 6-CDC (CDC onde todos os ciclos possuem comprimento 6). Relacionamos o SDC minimal com a 6-CDC em grafos cúbicos, e mostramos que existe apenas um grafo cúbico (K4) que admite SDC minimal e não admite 6-CDC.

Abstract

Sense of direction is a property of labeled graphs in which the edge labeling follows a consistent global scheme. This property is known to considerably reduce the complexity of severa1 distributed problems. In this work, we study a particular instance of sense of direction called chordal sense of direction (CSD). In special, we characterize the class of cubic graphs that admit a minimal CSD (a CSD with the minimum possible nurnber of labels). We generalize many results to the class of regular graphs. We prove that the class of regular graphs that admit a minimal CSD and the class of circulant graphs are equivalent, presenting an efficient (polynomial) way of recognizing this class when the graph's degree is fixed. We analyze another property, called the cycle double cover (CDC), and we describe a constructive method for generating cubic graphs that have a 6-CDC (a CDC in which every cycle has length 6). We relate minimal CSD with 6-CDC in cubic graphs, and show that there is only one cubic graph (K4) that has a minimal SDC but does not admit a BCDC.

Arquivo
Topo