Reconhecimento de Grafos Fino de Precedência
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.
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.