Reconhecimento de Grafos Fino de Precedência

• Flavia Bonomo Universidad de Buenos Aies
• Fabiano Oliveira UERJ
• Moysés Sampaio Jr UFRJ
• Jayme Szwarcfiter UFRJ

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

Resumo

The class of k-thin graphs have recently been introduced generalizing interval graphs. The complexity of the recognition of k-thin is open, even for fixed k 1. We introduce a subclass of the k-thin graphs, called precedence k-thin graphs, presenting an efficient recognition algorithm based on PQ trees.

Palavras-chave: interval graphs, PQ trees, k-thin graphs, precedence k-thin graphs

Referências

Bonomo, F., de Estrada, D. (2018). On the thinness and proper thinness of a graph. Discrete Applied Mathematics. In Press.

Bonomo, F., Mattia, S.„ Oriolo, G. (2011). Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem. Theoretical Computer Science, 412(45):6261–6268.

Booth, K. S., Lueker, G. S. (1976). Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal ofComputer and System Sciences, 13(3):335–379. Mannino, C., Oriolo, G., Ricci, F.„ Chandran, S. (2007). The stable set problem and the thinness of a graph. Operations Research Letters, 35:1–9.

Olariu, S. (1991). An optimal greedy heuristic to color interval graphs. Information Processing Letters, 37:21–25.