Um algoritmo polinomial para construção de um modelo de intervalo para grafos de intervalo
Resumo
Exploramos algumas propriedades fundamentais de grafos de intervalo, como a ausência de ciclos com quatro ou mais vértices e triplas asteroidais. Com base nessas propriedades, dado um grafo de intervalo G, desenvolvemos um algoritmo polinomial que usa o esquema de eliminação perfeita próprio dos grafos cordais, obtido através do algoritmo de busca em largura lexicográfica, para criar um modelo de intervalo para um grafo de intervalo G.
Palavras-chave:
Teoria dos Grafos, grafos de intervalo, modelo de intervalo, algoritmo
Referências
J. A. Bondy and U. S. R. Murty. Graph theory. Springer Publishing Company, Incorporated, 2008.
K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of computer and system sciences, 13(3):335–379, 1976.
T. H. Cormen. Algorithms unlocked. Editora Campus, 2013.
F. de Souza Oliveira. Sobre Ordens e Grafos de Intervalo. PhD thesis, Universidade Federal do Rio de Janeiro, 2011.
P. Feofiloff. Minicurso de análise de algoritmos. Departamento de Ciência da Computação, Instituto de Matemática e Estatística, Universidade de São Paulo, 2017. Disponível em: [link].
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York, USA, 1979.
F. Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Computing, 1(2):180–187, 1972.
M. C. Golumbic. Algorithmic graph theory and perfect graphs. Elsevier, 2004.
J. Kleinberg and E. Tardos. Algorithm design. Pearson Education India, 2006.
C. Lekkeikerker and J. Boland. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae, 1962.
K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of computer and system sciences, 13(3):335–379, 1976.
T. H. Cormen. Algorithms unlocked. Editora Campus, 2013.
F. de Souza Oliveira. Sobre Ordens e Grafos de Intervalo. PhD thesis, Universidade Federal do Rio de Janeiro, 2011.
P. Feofiloff. Minicurso de análise de algoritmos. Departamento de Ciência da Computação, Instituto de Matemática e Estatística, Universidade de São Paulo, 2017. Disponível em: [link].
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York, USA, 1979.
F. Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Computing, 1(2):180–187, 1972.
M. C. Golumbic. Algorithmic graph theory and perfect graphs. Elsevier, 2004.
J. Kleinberg and E. Tardos. Algorithm design. Pearson Education India, 2006.
C. Lekkeikerker and J. Boland. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae, 1962.
Publicado
05/12/2024
Como Citar
PEREIRA DE SOUZA, Ana Carolyne; NASCIMENTO, Julliano Rosa.
Um algoritmo polinomial para construção de um modelo de intervalo para grafos de intervalo. In: ESCOLA REGIONAL DE INFORMÁTICA DE GOIÁS (ERI-GO), 12. , 2024, Ceres/GO.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 61-70.
DOI: https://doi.org/10.5753/erigo.2024.4799.
