A polynomial algorithm for constructing an interval model for interval graphs

• Ana Carolyne Pereira de Souza UFG
• Julliano Rosa Nascimento UFG

DOI: https://doi.org/10.5753/erigo.2024.4799

Abstract

We explored some fundamental properties of interval graphs, such as the absence of cycles with four or more vertices and asteroidal triples. Based on these properties, given an interval graph G, we developed a polynomial algorithm that uses the perfect elimination scheme characteristic of chordal graphs, obtained through the lexicographic breadth-first search algorithm, to construct an interval model for an interval graph G.

Keywords: Graph Theory, interval graphs, interval model, algorithm

References

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.