{"id":554,"date":"2022-05-25T09:54:25","date_gmt":"2022-05-25T12:54:25","guid":{"rendered":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/?p=554"},"modified":"2022-05-25T09:54:27","modified_gmt":"2022-05-25T12:54:27","slug":"problema-da-coloracao-de-arestas-um-problema-de-1-milhao-de-dolares-e-alguns-avancos-dos-ultimos-40-anos","status":"publish","type":"post","link":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/?p=554","title":{"rendered":"Problema da Colora\u00e7\u00e3o de Arestas: um problema de 1 milh\u00e3o de d\u00f3lares\u00a0e alguns avan\u00e7os dos \u00faltimos 40 anos"},"content":{"rendered":"\n

Na ter\u00e7a-feira, 31 de maio, \u00e0s 19:30, o f\u00f3rum traz a palestra \u201cProblema da Colora\u00e7\u00e3o de Arestas: um problema de 1 milh\u00e3o de d\u00f3lares\u00a0e alguns avan\u00e7os dos \u00faltimos 40 anos\u201c,\u00a0<\/strong>com a Profa. Dra. Sheila Morais de Almeida (UTFPR-PG)<\/p>\n\n\n\n

Transmiss\u00e3o:\u00a0https:\/\/youtu.be\/gzpGpQ8ONSk<\/a>
Ative o lembrete e compartilhe!<\/p>\n\n\n\n

Resumo<\/strong>: Uma colora\u00e7\u00e3o de arestas de um grafo \u00e9 uma atribui\u00e7\u00e3o de cores para as arestas do grafo de maneira que arestas incidentes no mesmo v\u00e9rtice tenham cores diferentes. O Problema da Colora\u00e7\u00e3o de Arestas\u00a0 \u00e9 determinar o menor n\u00famero de cores para uma colora\u00e7\u00e3o de aresta de um grafo. Este problema surgiu no final do s\u00e9culo XIX, quando Alfred Kempe tentava encontrar uma prova para um outro problema famoso, conhecido como Problema das Quatro Cores. Em 1981, foi provado\u00a0que, dado um grafo G e um n\u00famero inteiro k, decidir se G tem uma colora\u00e7\u00e3o de arestas com k cores \u00e9 um Problema NP-completo.\u00a0 No ano 2000, o Clay Mathematics\u00a0Institute apresentou uma lista com os sete problemas matem\u00e1ticos que considerou os mais desafiadores deste mil\u00eanio. Nesta lista, est\u00e1 o problema P vs NP, que consiste em responder se existe um algoritmo polinomial\u00a0 para resolver algum dos problemas NP-completos.\u00a0O Clay Mathematics Institute oferece um pr\u00eamio de 1 milh\u00e3o de d\u00f3lares para o primeiro que apresentar solu\u00e7\u00e3o correta para cada um dos sete problemas.\u00a0Desta lista, apenas um problema foi resolvido, a Conjectura de Poincar\u00e9. Em 1985, David Johnson publicou a 6a edi\u00e7\u00e3o de sua coluna trimestral \u201cThe NP-completeness column: an ongoing guide\u201d.\u00a0 Nessa edi\u00e7\u00e3o, ele apresentou problemas conhecidos da Teoria dos Grafos e discutiu\u00a0a complexidade computacional desses problemas quando restritos a classes de grafos relevantes do ponto de vista algor\u00edtmico. Na lista h\u00e1 diversos problemas que s\u00e3o NP-completos, mesmo quando restritos a classes de grafos bastante conhecidas. Dentre os onze problemas\u00a0 considerados, o Problema da Colora\u00e7\u00e3o de Arestas destacou-se por ser aquele cuja complexidade computacional era desconhecida para o maior n\u00famero de classes de grafos (vinte e duas das trinta classes apresentadas). Trinta e seis anos depois, a complexidade computacional do Problema da Colora\u00e7\u00e3o de Arestas permanece em aberto para quatorze destas classes e o provou-se que este problema\u00a0\u00e9 NP-completo mesmo quando restrito a quatro das classes de grafos listadas.\u00a0 Dentre as classes de grafos para as quais a complexidade computacional do Problema da Colora\u00e7\u00e3o de Arestas permanece desconhecida, est\u00e3o os grafos split e os grafos de intervalos.\u00a0 Neste encontro vamos falar sobre os principais avan\u00e7os no conhecimento do Problema da Colora\u00e7\u00e3o de Arestas quando restrito a grafos split e grafos de intervalos.<\/p>\n\n\n\n

Bio<\/strong>: Sheila \u00e9 professora Adjunta da Universidade Tecnol\u00f3gica Federal do Paran\u00e1 (UTFPR), C\u00e2mpus Ponta Grossa, desde 2012.\u00a0 Bacharel (2002), Mestre (2005) e Doutora (2012) em Ci\u00eancia da Computa\u00e7\u00e3o pelo Instituto de Computa\u00e7\u00e3o da UNICAMP. Participou dos processos de abertura e reconhecimento dos cursos de gradua\u00e7\u00e3o em Ci\u00eancia da Computa\u00e7\u00e3o e Sistemas de Informa\u00e7\u00e3o da Universidade Federal do Mato Grosso do Sul \u2013 Ponta Por\u00e3, dos quais tamb\u00e9m foi coordenadora. Participou do processo de cria\u00e7\u00e3o e abertura do curso de P\u00f3s-Gradua\u00e7\u00e3o em Ci\u00eancia da Computa\u00e7\u00e3o da Universidade Tecnol\u00f3gica Federal do Paran\u00e1 \u2013 Ponta Grossa, do qual tamb\u00e9m foi coordenadora. \u00c9 revisora de artigos submetidos a confer\u00eancias e peri\u00f3dicos nacionais e internacionais. Participa dos comit\u00eas organizadores do Workshop de Pesquisa em Computa\u00e7\u00e3o dos Campos Gerais e do Latin\u00a0American Workshop\u00a0on Cliques in Graphs (2020 \u2013 2022). Atua como parecerista ad hoc na avalia\u00e7\u00e3o de projetos de pesquisa submetidos \u00e0 ag\u00eancias estaduais. Desenvolve pesquisas em Teoria dos Grafos h\u00e1 20 anos, atuando principalmente em problemas de colora\u00e7\u00e3o, caracteriza\u00e7\u00e3o e reconhecimento de subclasses de grafos perfeitos.<\/p>\n\n\n\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

Na ter\u00e7a-feira, 31 de maio, \u00e0s 19:30, o f\u00f3rum traz a palestra \u201cProblema da Colora\u00e7\u00e3o de Arestas: um problema de<\/p>\n","protected":false},"author":20,"featured_media":553,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[4],"tags":[152,153,154,150,148,149,151,86],"class_list":["post-554","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-seminarios","tag-arestas","tag-coloracao","tag-desafios","tag-grafos","tag-ponta-grossa","tag-sheila","tag-teoria-da-computacao","tag-utfpr"],"_links":{"self":[{"href":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/index.php?rest_route=\/wp\/v2\/posts\/554","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/index.php?rest_route=\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=554"}],"version-history":[{"count":1,"href":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/index.php?rest_route=\/wp\/v2\/posts\/554\/revisions"}],"predecessor-version":[{"id":555,"href":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/index.php?rest_route=\/wp\/v2\/posts\/554\/revisions\/555"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/index.php?rest_route=\/wp\/v2\/media\/553"}],"wp:attachment":[{"href":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=554"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=554"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/forppgcc-pr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=554"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}