Cohabitation of independent sets and dominating sets in trees

Löwenstein, Christian; Rautenbach, Dieter GND

We give a constructive characterization of trees that have a maximum independent set and a minimum dominating set which are disjoint and show that the corresponding decision problem is NP-complete for general graphs.

Zitieren

Zitierform:

Löwenstein, Christian / Rautenbach, Dieter: Cohabitation of independent sets and dominating sets in trees. 2008.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export