Este trabalho foi publicado pelo Galoá e tem um DOI depositado. Para citar este trabalho, use um dos padrões abaixo:
Caso você seja um dos co-autores e queira cadastrar esse trabalho no seu Currículo Lattes, use o seguinte código: doi > 10.59254/sbpo-2023-174973
Se você NUNCA registrou um DOI no seu Lattes, veja nosso tutorial!Nesse artigo, estudamos dois parâmetros de convexidade de grafos: tempo de iteração e número de posição geral. O primeiro foi definido na convexidade geodésica em 1981, mas sua complexidade estava ainda em aberto. O segundo foi definido na convexidade geodésica e provado $\NP$-difícil em 2018. Estendemos esses parâmetros para qualquer convexidade e provamos que o tempo de iteração é $\NP$-difícil na convexidade $P_3$ e, com isso, conseguimos provar que ele também é $\NP$-difícil na convexidade geodésica mesmo em grafos com diâmetro dois, uma questão natural que estava sem resposta desde quando o parâmetro foi definido, em 1981. Esses resultados são também importantes, visto que são os últimos dois resultados de $\NP$-completude que faltavam entre os dez parâmetros mais estudados de convexidade de grafos nas convexidades $P_3$ e geodésica. Finalmente também provamos que o número de posição geral da convexidade monofônica é $\NP$-difícil, $W[1]$-difícil e $n^{1-\varepsilon}$-inaproximável em tempo polinomial para qualquer $\varepsilon>0$ a menos que $\P=\NP$, mesmo em grafos com diâmetro dois.
Com ~200 mil publicações revisadas por pesquisadores do mundo todo, o Galoá impulsiona cientistas na descoberta de pesquisas de ponta por meio de nossa plataforma indexada.
Confira nossos produtos e como podemos ajudá-lo a dar mais alcance para sua pesquisa:
Esse proceedings é identificado por um DOI , para usar em citações ou referências bibliográficas. Atenção: este não é um DOI para o jornal e, como tal, não pode ser usado em Lattes para identificar um trabalho específico.
Verifique o link "Como citar" na página do trabalho, para ver como citar corretamente o artigo