UM ALGORITMO PARA DETERMINAR UM LIMITE SUPERIOR PARA O PROBLEMA DA CONTAGEM DE INTERVALO

Vol 53, 2021 - 139586
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

O emprego de técnicas de otimização combinatória no problema da contagem de intervalo foi explorado por Joos et al., resolvendo de forma eficiente uma versão restrita do problema da contagem de intervalo 2. Para o problema de determinar a contagem de intervalo geral, nenhuma técnica semelhante é conhecida atualmente. Elaboramos formulações de programação quadrática, levando a um algoritmo pseudopolinomial, para fornecer um limite superior na contagem de intervalo geral de ordens, que é empiricamente mostrado como próximo aos respectivos valores reais. Para a classe de semiordens, o limite superior é mostrado ser justo.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
  • 2 Universidade Federal do Rio de Janeiro
Eixo Temático
  • 19 - TAG – Teoria e Algoritmos em Grafos
Palavras-chave
Contagem de Intervalo
Limite superior algorítmico
Programação quadrática