On paths and trails in edge-colored graphs and digraphs

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorMartinhon, Carlos Alberto de Jesus-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2822582595834942-
Autor(es): dc.contributorNogueira, Loana Tito-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2537709612833688-
Autor(es): dc.contributorProtti, Fábio-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5898801580033554-
Autor(es): dc.contributorFigueiredo, Celina Miraglia Herrera de-
Autor(es): dc.contributorhttp://lattes.cnpq.br/3957046121364560-
Autor(es): dc.contributorFaria, Luerbio-
Autor(es): dc.contributorhttp://lattes.cnpq.br/3965328361563422-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5312565962811745-
Autor(es): dc.creatorLyra, Adria Ramos de-
Data de aceite: dc.date.accessioned2024-07-11T18:48:03Z-
Data de disponibilização: dc.date.available2024-07-11T18:48:03Z-
Data de envio: dc.date.issued2023-10-29-
Data de envio: dc.date.issued2023-10-29-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/30999-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/777858-
Descrição: dc.descriptionNeste 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.descriptionWe 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.description98 p.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languageen-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectGrafos e digrafos com cores nas arestas-
Palavras-chave: dc.subjectCaminhos e trilhas monocromáticos e propriamente coloridos-
Palavras-chave: dc.subjectTorneios com cores nas arestas-
Palavras-chave: dc.subjectOtimização em grafos com custo de conexão entre as cores-
Palavras-chave: dc.subjectGrafo-
Palavras-chave: dc.subjectOtimização (Computação)-
Palavras-chave: dc.subjectAlgoritmo em grafos-
Palavras-chave: dc.subjectEdge-colored graphs and digraphs-
Palavras-chave: dc.subjectProperly edge-colored paths/trails-
Palavras-chave: dc.subjectMonochromatic paths-
Palavras-chave: dc.subjectEdge-colored tournaments-
Palavras-chave: dc.subjectReload optimization-
Título: dc.titleOn paths and trails in edge-colored graphs and digraphs-
Título: dc.titleSobre caminhos e trilhas em grafos e digrafos com cores nas arestas-
Tipo de arquivo: dc.typeTese-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.