Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Martinhon, Carlos Alberto de Jesus | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/2822582595834942 | - |
Autor(es): dc.contributor | Nogueira, Loana Tito | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/2537709612833688 | - |
Autor(es): dc.contributor | Protti, Fábio | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/5898801580033554 | - |
Autor(es): dc.contributor | Figueiredo, Celina Miraglia Herrera de | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/3957046121364560 | - |
Autor(es): dc.contributor | Faria, Luerbio | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/3965328361563422 | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/5312565962811745 | - |
Autor(es): dc.creator | Lyra, Adria Ramos de | - |
Data de aceite: dc.date.accessioned | 2024-07-11T18:48:03Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T18:48:03Z | - |
Data de envio: dc.date.issued | 2023-10-29 | - |
Data de envio: dc.date.issued | 2023-10-29 | - |
Fonte completa do material: dc.identifier | http://app.uff.br/riuff/handle/1/30999 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/777858 | - |
Descrição: dc.description | Neste trabalho, estuda-se diferentes questões sobre s-t caminhos e trilhas propriamente coloridos em grafos e digrafos com cores nas aretas. Dado Gc um grafo com c cores nas aretas sem trilhas fechadas propriamente coloridas, apresenta-se um procedimento polinomial para determinação de s-t trilhas propriamente coloridas que visitam todos os vértices de Gc um determinado número de vezes. Como consequência imediata, resolve-se polinomialmente o problema do caminho Hamiltoniano e Euleriano para esta classe particular de grafos. Além disso, prova-se que encontrar dois caminhos propriamente coloridos disjuntos por vértices ou arestas em Gc contendo no máximo L > 0 arestas é NP-completo forte. Também, mostra-se que achar dois caminhos monocromáticos disjuntos por vértices, com cores diferentes, em um grafo Gc qualquer é NP-completo. Considerando digrafos com cores nas arestas, mostra-se que determinar um s-t caminho direcionado propriamente colorido é NP-completo mesmo para c = (n2). Se o digrafo for um torneio com cores nas arestas, mostra-se que decidir se este contém um circuito propriamente colorido passando por um vértice v (ou um caminho Hamiltoniano direcionado) é NP-completo. Como consequência, resolve-se uma versão mais fraca de um problema proposto em [30]. Além disso, considerando-se trilhas ao invés de caminhos, mostra-se que alguns problemas são polinomiais para s-t trilhas direcionadas propriamente coloridas. Considera-se também s-t caminhos, trilhas e passeios em grafos coloridos com custos de conexão entre as aretas. Sempre que se muda de uma cor para outra em um passeio tem-se um custo de conexão ri,j associado, onde i e j são as cores das sucessivas arestas do passeio. O objetivo é encontrar uma rota cujo custo total de conexão seja minimizado. Algoritmos polinomiais e provas de NP-dificuldade são apresentados para casos particulares: quando a desigualdade triangular é satifeita ou não, quando os custos de conexões são simétricos (i.e., ri,j = rj,i) ou assimétricos. Também são investigados instâncias com grau máximo limitado e grafos planares | - |
Descrição: dc.description | We deal with different algorithmic questions regarding properly edge-colored s-t paths/trails in edge-colored graphs and digraphs. Given a c-edge-colored graph Gc with no properly edge-colored closed trails, we present a polynomial time procedure for the determination of properly edge-colored s-t trails visiting all vertices of Gc a predefined number of times. As an immediate consequence, we polynomially solve the Hamiltonian path (resp., Eulerian trail) problem for this particular class of graphs. In addition, we prove that to check whether Gc contains 2 properly edge-colored s-t paths/trails with length at most L > 0 is NP-complete in the strong sense. Besides, we also show that if Gc is a general c-edge-colored graph, to find 2 monochromatic vertex disjoint s-t paths with different colors is NP-complete. Regarding c-edge-colored digraphs, we show that the determination of a directed properly edge-colored s-t path is NP-complete in digraphs with c = (n2) colors. If the digraph is a c-edge-colored tournament, we show that deciding whether it contains a properly edge-colored circuit passing through a given vertex v (resp., directed s-t Hamiltonian path) is NP-complete. As a consequence, we solve a weak version of an open problem posed in [30]. In addition, we show that several problems are polynomial if we deal with directed properly edge-colored s-t trails instead of directed properly edge-colored s-t paths. We also consider s-t paths, trails and walks with reload costs over c-edge-colored graphs. Each time a vertex is crossed by a walk there is an associated non-negative reload cost ri,j , where i and j denote, respectively, the colors of successive edges in this walk. The goal is to find a route whose total reload cost is minimized. Polynomial algorithms and proofs ofNP-hardness are given for particular cases: when the triangle inequality is satisfied or not, when reload costs are symmetric (i.e., ri,j = rj,i) or asymmetric. We also investigate bounded degree graphs and planar graphs | - |
Descrição: dc.description | 98 p. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | en | - |
Direitos: dc.rights | Open Access | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Grafos e digrafos com cores nas arestas | - |
Palavras-chave: dc.subject | Caminhos e trilhas monocromáticos e propriamente coloridos | - |
Palavras-chave: dc.subject | Torneios com cores nas arestas | - |
Palavras-chave: dc.subject | Otimização em grafos com custo de conexão entre as cores | - |
Palavras-chave: dc.subject | Grafo | - |
Palavras-chave: dc.subject | Otimização (Computação) | - |
Palavras-chave: dc.subject | Algoritmo em grafos | - |
Palavras-chave: dc.subject | Edge-colored graphs and digraphs | - |
Palavras-chave: dc.subject | Properly edge-colored paths/trails | - |
Palavras-chave: dc.subject | Monochromatic paths | - |
Palavras-chave: dc.subject | Edge-colored tournaments | - |
Palavras-chave: dc.subject | Reload optimization | - |
Título: dc.title | On paths and trails in edge-colored graphs and digraphs | - |
Título: dc.title | Sobre caminhos e trilhas em grafos e digrafos com cores nas arestas | - |
Tipo de arquivo: dc.type | Tese | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: