{"id":{"repo_id":"brazil-ufba","oai_identifier":"oai:repositorio.ufba.br:ri/39322"},"canonical_url":"https://search.dev.ndltd.org/etd/brazil-ufba/oai:repositorio.ufba.br:ri/39322","repository":{"repo_id":"brazil-ufba","name":"Brazil UFBA","base_url":"https://repositorio.ufba.br/oai/request"},"display":{"title":"Application of biased random-key genetic algorithm and formulations for the Grundy coloring problem and the connected Grundy coloring problem","abstract":"Dado um grafo G, seu número de Grundy Γ(G) define o comportamento de pior caso para a conhecida e amplamente utilizada heurística de coloração gulosa first-fit. Mais especificamente, Γ(G) é o maior k para o qual uma k-coloração pode ser obtida com a heurística first-fit. O número de Grundy conexo Γc(G) fornece o comportamento do pior caso para a heurística de coloração first-fit conexa, ou seja, aquela em que cada vértice a ser colorido, exceto o primeiro, é adicionado adjacente a um vértice já colorido. Ambos os problemas são NP-difíceis. Nesta dissertação, apresentamos abordagens heurísticas e exatas para o problema da coloração de Grundy e o problema de coloração de Grundy conexo, que são problemas de otimização consistindo na obtenção do número de Grundy e do número de Grundy conexo, respectivamente. Nesse estudo é proposto o uso do algoritmo genético de chaves aleatórias viesado (Biased random-key genetic algorithm - BRKGA) e do uso de formulações de programação inteira usando uma abordagem mais tradicional (padrão) e uma por representativos. Também é proposto um novo limite superior combinatório que é válido para ambos os problemas e um algoritmo usando programação dinâmica para o seu cálculo. Os experimentos computacionais mostram que o novo limite superior pode melhorar o limite para vários casos em relação a um limite combinatório bem estabelecido disponível na literatura. Os resultados também evidenciam que a formulação por representativos tem um desempenho geral superior que a formulação padrão, alcançando melhores resultados para as instâncias mais densas, enquanto esta última tem melhor desempenho para as mais esparsas para o problema dos números de Grundy. Contudo mostramos que este tipo de formulações com programação inteira são computacionalmente impraticáveis para a versão conexa. Além disso, o BRKGA pode encontrar soluções de alta qualidade para ambos os problemas e pode ser usado com confiança em grandes instâncias onde as formulações falham para o problema da coloração de Grundy","abstract_html":"Dado um grafo G, seu número de Grundy Γ(G) define o comportamento de pior caso para a conhecida e amplamente utilizada heurística de coloração gulosa first-fit. Mais especificamente, Γ(G) é o maior k para o qual uma k-coloração pode ser obtida com a heurística first-fit. O número de Grundy conexo Γc(G) fornece o comportamento do pior caso para a heurística de coloração first-fit conexa, ou seja, aquela em que cada vértice a ser colorido, exceto o primeiro, é adicionado adjacente a um vértice já colorido. Ambos os problemas são NP-difíceis. Nesta dissertação, apresentamos abordagens heurísticas e exatas para o problema da coloração de Grundy e o problema de coloração de Grundy conexo, que são problemas de otimização consistindo na obtenção do número de Grundy e do número de Grundy conexo, respectivamente. Nesse estudo é proposto o uso do algoritmo genético de chaves aleatórias viesado (Biased random-key genetic algorithm - BRKGA) e do uso de formulações de programação inteira usando uma abordagem mais tradicional (padrão) e uma por representativos. Também é proposto um novo limite superior combinatório que é válido para ambos os problemas e um algoritmo usando programação dinâmica para o seu cálculo. Os experimentos computacionais mostram que o novo limite superior pode melhorar o limite para vários casos em relação a um limite combinatório bem estabelecido disponível na literatura. Os resultados também evidenciam que a formulação por representativos tem um desempenho geral superior que a formulação padrão, alcançando melhores resultados para as instâncias mais densas, enquanto esta última tem melhor desempenho para as mais esparsas para o problema dos números de Grundy. Contudo mostramos que este tipo de formulações com programação inteira são computacionalmente impraticáveis para a versão conexa. Além disso, o BRKGA pode encontrar soluções de alta qualidade para ambos os problemas e pode ser usado com confiança em grandes instâncias onde as formulações falham para o problema da coloração de Grundy","abstract_has_math":false,"creators":["Silva, Mateus Carvalho"],"institution":"Universidade Federal da Bahia","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-12-13","date_published":"2023-12-13","updated_at":"2026-07-27T22:08:00Z","subjects":["Otimização combinatória","Coloração de grafos","Número de Grundy","BRKGA","Análise de pior caso"],"languages":["eng"],"rights":["Acesso Aberto"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://repositorio.ufba.br/handle/ri/39322","outbound_label":"Repository record","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Silva, Mateus Carvalho"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2024-04-26T21:51:54Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2024-04-26","2024-04-26T21:51:54Z"]},{"key":"dc:date.issued","label":"Date","values":["2023-12-13"]},{"key":"dc:publisher","label":"Institution","values":["Universidade Federal da Bahia"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Instituto de Computação - IC"]},{"key":"dc:type","label":"Dc Type","values":["Dissertação"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Otimização combinatória","Coloração de grafos","Número de Grundy","BRKGA","Análise de pior caso"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Acesso Aberto"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://repositorio.ufba.br/handle/ri/39322"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Dado um grafo G, seu número de Grundy Γ(G) define o comportamento de pior caso para a conhecida e amplamente utilizada heurística de coloração gulosa first-fit. Mais especificamente, Γ(G) é o maior k para o qual uma k-coloração pode ser obtida com a heurística first-fit. O número de Grundy conexo Γc(G) fornece o comportamento do pior caso para a heurística de coloração first-fit conexa, ou seja, aquela em que cada vértice a ser colorido, exceto o primeiro, é adicionado adjacente a um vértice já colorido. Ambos os problemas são NP-difíceis. Nesta dissertação, apresentamos abordagens heurísticas e exatas para o problema da coloração de Grundy e o problema de coloração de Grundy conexo, que são problemas de otimização consistindo na obtenção do número de Grundy e do número de Grundy conexo, respectivamente. Nesse estudo é proposto o uso do algoritmo genético de chaves aleatórias viesado (Biased random-key genetic algorithm - BRKGA) e do uso de formulações de programação inteira usando uma abordagem mais tradicional (padrão) e uma por representativos. Também é proposto um novo limite superior combinatório que é válido para ambos os problemas e um algoritmo usando programação dinâmica para o seu cálculo. Os experimentos computacionais mostram que o novo limite superior pode melhorar o limite para vários casos em relação a um limite combinatório bem estabelecido disponível na literatura. Os resultados também evidenciam que a formulação por representativos tem um desempenho geral superior que a formulação padrão, alcançando melhores resultados para as instâncias mais densas, enquanto esta última tem melhor desempenho para as mais esparsas para o problema dos números de Grundy. Contudo mostramos que este tipo de formulações com programação inteira são computacionalmente impraticáveis para a versão conexa. Além disso, o BRKGA pode encontrar soluções de alta qualidade para ambos os problemas e pode ser usado com confiança em grandes instâncias onde as formulações falham para o problema da coloração de Grundy"]},{"key":"dc:title","label":"Title","values":["Application of biased random-key genetic algorithm and formulations for the Grundy coloring problem and the connected Grundy coloring problem"]}]}],"canonical_facts":{"dc:creator":["Silva, Mateus Carvalho"],"dc:date.accessioned":["2024-04-26T21:51:54Z"],"dc:date.available":["2024-04-26","2024-04-26T21:51:54Z"],"dc:date.issued":["2023-12-13"],"dc:description.abstract":["Dado um grafo G, seu número de Grundy Γ(G) define o comportamento de pior caso para a conhecida e amplamente utilizada heurística de coloração gulosa first-fit. Mais especificamente, Γ(G) é o maior k para o qual uma k-coloração pode ser obtida com a heurística first-fit. O número de Grundy conexo Γc(G) fornece o comportamento do pior caso para a heurística de coloração first-fit conexa, ou seja, aquela em que cada vértice a ser colorido, exceto o primeiro, é adicionado adjacente a um vértice já colorido. Ambos os problemas são NP-difíceis. Nesta dissertação, apresentamos abordagens heurísticas e exatas para o problema da coloração de Grundy e o problema de coloração de Grundy conexo, que são problemas de otimização consistindo na obtenção do número de Grundy e do número de Grundy conexo, respectivamente. Nesse estudo é proposto o uso do algoritmo genético de chaves aleatórias viesado (Biased random-key genetic algorithm - BRKGA) e do uso de formulações de programação inteira usando uma abordagem mais tradicional (padrão) e uma por representativos. Também é proposto um novo limite superior combinatório que é válido para ambos os problemas e um algoritmo usando programação dinâmica para o seu cálculo. Os experimentos computacionais mostram que o novo limite superior pode melhorar o limite para vários casos em relação a um limite combinatório bem estabelecido disponível na literatura. Os resultados também evidenciam que a formulação por representativos tem um desempenho geral superior que a formulação padrão, alcançando melhores resultados para as instâncias mais densas, enquanto esta última tem melhor desempenho para as mais esparsas para o problema dos números de Grundy. Contudo mostramos que este tipo de formulações com programação inteira são computacionalmente impraticáveis para a versão conexa. Além disso, o BRKGA pode encontrar soluções de alta qualidade para ambos os problemas e pode ser usado com confiança em grandes instâncias onde as formulações falham para o problema da coloração de Grundy"],"dc:identifier.uri":["https://repositorio.ufba.br/handle/ri/39322"],"dc:language":["eng"],"dc:publisher":["Universidade Federal da Bahia"],"dc:publisher.department":["Instituto de Computação - IC"],"dc:rights":["Acesso Aberto"],"dc:subject":["Otimização combinatória","Coloração de grafos","Número de Grundy","BRKGA","Análise de pior caso"],"dc:title":["Application of biased random-key genetic algorithm and formulations for the Grundy coloring problem and the connected Grundy coloring problem"],"dc:type":["Dissertação"]},"updated_at":"2026-07-27T22:08:00Z"}