Toleransgraf

I grafteorin är en toleransgraf en oriktad graf där varje vertex kan representeras av ett slutet intervall och ett reellt tal som kallas dess tolerans, på ett sådant sätt att två hörn är intill varandra i grafen när deras intervall överlappar i en längd som är åtminstone minimum av deras två toleranser. Denna klass av grafer introducerades 1982 av Martin Charles Golumbic och Clyde Monma, som använde dem för att modellera schemaläggningsproblem där uppgifterna som ska modelleras kan dela resurser under begränsade tidsperioder.

Varje intervallgraf är en toleransgraf. Komplementgrafen för varje toleransgraf är en perfekt beställningsbar graf , av vilken det följer att själva toleransgraferna är perfekta grafer .

Det är NP-komplett för att avgöra om en given graf är en toleransgraf. Men eftersom toleransgrafer är perfekta grafer, kan många algoritmiska problem som är svåra för andra klasser av grafer, inklusive graffärgning och klickproblemet , lösas i polynomtid på toleransgrafer.