Kruskal Algorithm

In 3 it was presented a way to i n troduce fuzzy edges and v ertices in graphs to m anipulate incertainty a n d imprecision in images. This procedure provide more exibility i n s e g m entation techniques based on pyramid strutures but i t i n troduces several topologic problems to m erge regions. This work presents strategies to realize good region merges and t o a v oid connectivity problems.

In this study, the authors propose a soft-switching filter to improve the performance of recent colour image smoothing filters when processing homogeneous image regions. The authors use a recent filter mixed with the classical arithmetic mean filter (AMF). The recent method is used to process image pixels close to edges, texture and details and the AMF is only used to process homogeneous regions. To this end, the authors propose a method based on the graph theory to distinguish image details and homogeneous regions and to perform a soft switching between the two filters. Experimental results show that the proposed method provides improved results which supports the appropriateness of the graph theory-based method and suggests that the same structure can be used to improve the performance of other non-linear colour image smoothing methods.

In this study, the authors propose a soft-switching filter to improve the performance of recent colour image smoothing filters when processing homogeneous image regions. The authors use a recent filter mixed with the classical arithmetic mean filter (AMF). The recent method is used to process image pixels close to edges, texture and details and the AMF is only used to process homogeneous regions. To this end, the authors propose a method based on the graph theory to distinguish image details and homogeneous regions and to perform a soft switching between the two filters. Experimental results show that the proposed method provides improved results which supports the appropriateness of the graph theory-based method and suggests that the same structure can be used to improve the performance of other non-linear colour image smoothing methods.

Abstract: Let V nk denote the set of all n-dimensional vectors whose components are integers between 0 and k? 1. A subset of V nk is called a code. A code C is said to be an R-covering of V nk if, for all y 2 V nk, there exists a vector x 2 C within Hamming distance R from y. The covering problem is de ned as the problem of nding a covering code of minimum size. In this paper we formulate this problem as a dominating set problem in a graph and propose a Tabu Search algorithm to solve it. The computational results obtained by our ...

Recebido em 9 outubro 2018 / Aceito em 12 fevereiro 2019 RESUMO. Neste artigo é proposto um modelo de programac ¸ão por metas estendido aplicado ao planejamento de radioterapia, em que foi encontrada a melhor combinac ¸ão de pesos para as metas a serem atingidas. O modelo foi aplicado a um caso real de câncer de próstata e resolvido pelo software CPLEX, em que foi utilizado o Método de Pontos Interiores Barreira Logarítmica como método de resoluc ¸ão. Palavras-chave: programac ¸ão por metas, otimizac ¸ão, radioterapia. 1 INTRODUC ¸ÃO O câncer é a segunda causa de mortes por doenc ¸as no Brasil segundo o INCA (Instituto Nacional do Câncer) [5], com expectativa para o ano de 2018 uma ocorrência de aproximadamente 600 mil novos casos. Entre as modalidades ou métodos de tratamento, sendo eles curativo e/ou paliativo, destaca-se a radioterapia, a qual é baseada no fato que células cancerígenas quando irradiadas são alteradas, mudando sua estrutura por completo. Atualmente esta técnica está entre as principais escolhas do setor oncológico no tratamento tanto de tumores malignos quanto benignos, abrangendo cerca de 60% a 70% dos seus pacientes . A partir do momento que células são irradiadas por um campo de radiac ¸ão externo, uma reac ¸ão secundária em cadeia faz com que radicais livres fluam por todo material celular, onde tanto a regiões de órgãos críticos quanto de tecidos tumorais sejam atingidos. Porém se a dose aplicada se mostrar inferior à mínima necessária as células cancerígenas ainda possuirão um grande potencial

This work consists in the application of an optimized breadth-first search (BFS) algorithm to select a couple of link-and-node-disjoint shortest-path between the two most remote users within an optical access network. Our results showed that while the average execution time of the original BFS algorithm was 12.23 seconds that of the optimized BFS was 10.80 seconds, which means a reduction of 11.69 percent of the average computing time. In future works we intend to apply the modified BFS algorithm to a generic optical network and evaluate its performance for different mesh size, node concentration and random link arrangement. Index Terms-Breadth-first search, Network optimization, Optical networks, Routing, Shortest-path search algorithm. I. INTRODUÇÃO A DEMANDA crescente de uso de dados, fomentada pelo maior acesso aos dispositivos móveis, pela adesão maciçà as redes sociais e pelo uso em larga escala de aplicações em tempo real, como download de filmes e jogos em rede, resultou em uma maior abrangência e complexidade das redeś opticas atuais caracterizadas por uma grande carga de tráfego [1]. Neste contexto, algoritmos computacionais têm sido a ferramenta mais eficiente tanto no projeto quanto na gestão de tráfego de dados das redes, realizando funções como a escolha da rota (routing), a definição do melhor ou menor caminho e do caminho de proteção, a escolha do melhor canal de comunicação e ainda ações de contingência e contençãoàs falhas [1] [2]. Outras iniciativas de otimização do emprego dos recursos disponíveis nas redesópticas envolvem o apri-moramento da qualidade de serviço em ações de roteamento através do emprego de algoritmos genéticos [3], a definição do nívelótimo da potência lançada na fibra para combater as não-linearidades, a dispersão do sinal e maximizar o número de usuários simultâneos [4] e também a virtualização das funções da rede de modo a potencializar o compartilhamento dos recursos da camada física [5]. Entre os algoritmos de busca mais populares estão o al-goritmo de Dijkstra [6] e o algoritmo de busca em largura (Breadth-First Search-BFS) [7]. O algoritmo Dijkstraé considerado um algoritmo "greedy", ou seja, escolhe a melhor opção a cada passo, sem considerar passos futuros em seu processo de busca do menor caminho entre dois nós da rede, sendo a métrica mais usual a distância geográfica [1]. Por sua vez, o algoritmo BFS usa como métrica o número de enlaces (hops) para retornar a melhor solução tomando como base as G. L. Andrade, Universidade Federal do Pampa, Alegrete, Rio Grande do Sul, Brasil, [email protected]. D. H. Thomas, Universidade Federal do Pampa, Alegrete, Rio Grande do Sul, Brasil, [email protected]. informações gerais da rede em questão, ou seja, dentre todos os caminhos possíveis busca primeiramente aqueles constituídos de umúnico hop, depois aqueles com dois hops e assim sucessivamente, fornecendo ao final o caminho com menor número de hops ou a classificação destes em ordem crescente do número de hops [1]. O algoritmo BFS, também conhecido como busca em amplitude [8],é um algoritmo fundamental da teoria dos grafos, comumente utilizado para realizar a busca dos caminhos mais curtos em grafos não ponderados, dados os nós de origem e destino [7] [9]. Recentemente este algoritmo vem sendo utilizado para solucionar problemas computacionais desafi-adores em redes Ponto-a-Ponto [10] [11] [12], ondeé utilizado para a localização de pontos para a formação da rede [12] e também para escolher a melhor rota de compartilhamento de mensagens ou arquivos entre os nós da rede [11]. O uso do BFS tambémé frequente em redes elétricas inteligentes com o objetivo de minimizar o número de saltos entre os nós da rede em malha e obter o posicionamento ideal de concentradores GPRS (General Packet Radio Service) [13] [14]. O serviço GPRSé uma extensão do GSM (Global System for Mobile Communications), com a diferença que a transferência dos dadosé através realizada através da comutação de pacotes. O GSMé o padrão celular digital pan-Europeu publicado pelo ETSI (European Telecommunications Standards Institute para transmissão de dados em telefonia móvel [15] [16]. Da mesma forma, pesquisas recentes tem explorado o uso do BFS em processadores multicore [8] [17] [18] [19]. Estes processadores possuem múltiplos núcleos de processamento para realizar diversas tarefas simultâneas (paralelas) e assim obter desem-penho superior quando comparados aos processadores de uḿ unico núcleo. Neste caso, o BFSé utilizado em aplicações paralelas, ou seja, atua entre os diversos núcleos do proces-sador para reduzir o tempo de busca. Além disso, o BFSé empregado para reduzir o tempo de acesso em processamentos computacionais que empregam memória distribuída [20]. O algoritmo BFS também pode ser utilizado em jogos digitais, como o Maze Runner [21] e o Bomberman [22]. Ambos são jogos baseados em labirintos em que o objetivó e vencer o adversário através do emprego do menor caminho para a saída. Algoritmos de busca apresentam aplicação crescente para realizar o roteamento em redesópticas, ou seja, para encontrar o menor caminho (shortest-path) entre usuários destas redes [2], sendo que o menor caminho será a soma das métricas dos enlaces que compõem o caminho. As métricas são as mais variadas possíveis, sendo bastante comuns a distância geográfica, o número de hops e a probabilidade de disponibil-Authorized licensed use limited to: MANIPAL INSTITUTE OF TECHNOLOGY. Downloaded on January 05,2021 at 06:02:50 UTC from IEEE Xplore. Restrictions apply.

Routing protocols present a latency, i.e. a time interval spent to up- date all routing tables, after the topology changes. During the convergence latency interval several packets and connections may be lost. This work pro- poses a new strategy for a dynamic routing, in which intermediate routers, that may hold more recent information about the current state of the topology,

Este trabalho tem por objetivo realizar um estudo sobre o problema de Alocação de Tutores em Aplicações de Provas nos polos do Cederj. Este problema consiste em encontrar uma alocação de disciplinas e tutores em salas de aula satisfazendo um conjunto de regras para a realização das avaliações presenciais. Neste trabalho, descrevemos as regras impostas pelos polos para caracterização de uma alocação viável, e com base nestas, formulamos o problema de Alocação de Tutores em Aplicações de Provas. Em nossa abordagem, dividimos o problema em duas etapas: a primeira consiste em agrupar disciplinas em salas de aula de forma a ocupar o menor número de salas possíveis; e a segunda consiste em alocar tutores nas salas de aula satisfazendo as regras impostas pelos polos. Para solucionar esse problema, modelamos: (i) o agrupamento de disciplinas em salas de aula como uma variação do problema Bin Packing; (ii) alocação de tutores nas salas de aula como uma instância do problema de emparelhamento 3-dimensional em grafos.

Este trabalho tem por objetivo realizar um estudo sobre o problema de Alocação de Tutores em Aplicações de Provas nos polos do Cederj. Este problema consiste em encontrar uma alocação de disciplinas e tutores em salas de aula satisfazendo um conjunto de regras para a realização das avaliações presenciais. Neste trabalho, descrevemos as regras impostas pelos polos para caracterização de uma alocação viável, e com base nestas, formulamos o problema de Alocação de Tutores em Aplicações de Provas. Em nossa abordagem, dividimos o problema em duas etapas: a primeira consiste em agrupar disciplinas em salas de aula de forma a ocupar o menor número de salas possíveis; e a segunda consiste em alocar tutores nas salas de aula satisfazendo as regras impostas pelos polos. Para solucionar esse problema, modelamos: (i) o agrupamento de disciplinas em salas de aula como uma variação do problema Bin Packing; (ii) alocação de tutores nas salas de aula como uma instância do problema de emparelhamento 3-dimensional em grafos.

O aumento crescente do número de veículos
nos grandes centros urbanos tem acelerado o processo de
deterioração das vias públicas, que não suportam tal fluxo. Esse
problema é, em geral, solucionado parcialmente por operações
chamadas de “tapa buracos”, cujo custo é relativamente baixo
mas cuja durabilidade é, por outro lado, curta. Este artigo propõe uma alternativa para o planejamento eficaz da manutenção de vias públicas urbanas. Trata-se de uma abordagem estruturada na teoria dos grafos que parte do modelo de uma malha viária e define uma sequência de operações matemáticas que refinam esse modelo de tal modo que passa a ser possível derivar um caminho a ser manutenido. Esse caminho preserva certas propriedades
desejáveis em vias públicas, como a conexidade entre pontos, a
redução de distâncias, de gastos, otimização de recursos, etc. A
aplicabilidade da abordagem é ilustrada por meio de um exemplo de modelagem que recebe como entrada um trecho de vias, obtido do mapa real da cidade de Pato Branco - PR, e aponta como resultado um plano para a manutenção daquele trecho, obedecendo a certas especificações predefinidas. A viabilidade da abordagem é ilustrada por meio de um comparativo envolvendo dados reais de custos de manutenção de vias. Os resultados apontam para um índice significativo de economia.

This work provides a general framework for the analysis and synthesis of a class of relative sensing networks (RSN) in the context of its H∞ performance. In an RSN, the underlying connection topology couples each agent at their outputs. A distinction is made between RSN with homogeneous agent dynamics and RSN with heterogeneous dynamics. In both cases, explicit graph theoretic expressions and bounds for the H∞ performance are derived. The H∞ performance is structure dependent and related to the spectral radius of the graph Laplacian. The analysis results are then used to develop synthesis methods for RSNs. Using results from robust semi-definite programming, a synthesis procedure for the design of a robust sensing topology is derived.

This work provides a general framework for the analysis and synthesis of a class of linear networked dynamic systems (NDS). We focus our attention on NDS where the underlying connection topology couples the agents at their outputs. A distinction is made between NDS with homogeneous agent dynamics and NDS with heterogeneous agent dynamics. In the homogeneous setting, the H2 norm expression reduces to the Frobenius norm of the underlying connection topology incidence matrix, E(G), scaled by the H2 norm of the agents comprising the NDS. In the heterogeneous case, the H2 norm becomes the weighted Frobenius norm of the incidence matrix, where the weights appear on the nodes of the graph. The H2 norm characterization is then used to synthesize NDS with certain H2 performance. Specifically, a semi-definite programming solution is presented to design a local controller for each agent when the underlying topology is fixed. A solution using Kruskal's algorithm for finding a minimum weight spanning tree is used to design the optimal NDS topology given fixed agent dynamics.