Limite superior algorítmico para a contagem de intervalo

• Lívia Salgado Medeiros UERJ http://orcid.org/0000-0002-4422-1812
• Fabiano de Souza Oliveira UERJ https://orcid.org/0000-0002-8498-2472
• Jayme Luiz Szwarcfiter UERJ / UFRJ https://orcid.org/0000-0002-7538-7305

DOI: https://doi.org/10.5753/etc.2021.16367

Resumo

O emprego de técnicas de otimização combinatória associadas ao 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 determinação da 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 ao respectivo valores reais. Para a classe de semiordens, o limite superior é mostrado como restrito.

Palavras-chave: Contagem de intervalo, Limite superior algorítmico, Programação quadrática

Referências

Fishburn, P. (1985).Interval Orders and Interval Graphs. John Wiley and Sons.

Joos, F., Lowenstein, C., Oliveira, F. S., Rautenbach, D., and Szwarcfiter, J. L. (2014). Graphs of interval count two with a given partition.Inf. Process. Lett., 114:542–546

Klavík, P., Otachi, Y., and Sejnoha, J. (2019). On the classes of interval graphs of limited nesting and count of lengths.Algorithmica, 81:1490–1511.

Kozlov, M. K., Tarasov, S. P., and Khachiyan, L. G. (1981). The polynomial solvability of convex quadratic programming.Comput. Maths. Math. Phys, 20(5):223–228.

Leibowitz, R., Assmann, S. F., and Peck, G. W. (1982). The interval count of a graph.SIAM J. Alg. Discr. Meth., 3(4):485–494.

Medeiros, L. S., Oliveira, F. S., and Szwarcfiter, J. L. (2019). Two problems on interval counting. Electron. Notes Theor. Comput. Sci., 346:625–643.