Reconhecimento de Grafos Fino de Precedência

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

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.
Publicado
02/07/2019
BONOMO, Flavia; OLIVEIRA, Fabiano ; SAMPAIO JR, Moysés ; SZWARCFITER, Jayme . Reconhecimento de Grafos Fino de Precedência. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 4. , 2019, Belém. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2019.6396.