Technical Report 392-1994
- Title
- Triangulating Multitolerance Graphs
- Author
- Andreas Parra
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
- Classification
-
not available
- Keywords
-
not available
-
In this paper we introduce a new class of graphs which generalizes both the tolerance and the trapezoid graphs, the {it multitolerance graphs}. We show that the difference between the pathwidth and the treewidth of a multitolerance graph is at most one, and we develop an algorithm which solves the minimum fill-in problem for a multitolerance graph with a given representation in polynomial time. These results complement recent results by Habib and Möhring hm92,m93} about the treewidth and pathwidth of cocomparability graphs and graphs without asteroidal triples, and by Kloks et al. kbmk93} about the minimum fill-in problem.