Reconhecimento de Grafos Fino de Precedência - Bonomo, Flavia; Oliveira, Fabiano; Sampaio Jr, Moysés; Szwarcfiter, Jayme (Anais do Encontro de Teoria da Computação (ETC); 2019: Anais do IV Encontro de Teoria da Computação, 2019)
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.