Co-Graph

In der Informatik ist ein Co-Graph ein ungerichteter Graph ${\displaystyle G=(V,E)}$, welcher sich mit bestimmten elementaren Operationen konstruieren lässt. Auf Co-Graphen lassen sich viele schwere Probleme wie z. B. CLIQUE und das damit eng verwandte UNABHÄNGIGE MENGE sowie KNOTENÜBERDECKUNG in Linearzeit lösen.