Cohabitation of independent sets and dominating sets in trees

Löwenstein, Christian; Rautenbach, Dieter

Veröffentlicht

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.

Vorschau

Einordnung

In Serie:: Preprint / Technische Universität Ilmenau, Institut für Mathematik
Vol. 08-11 (16.04.2008)
Datum der Erstellung:: 16.04.2008
Datum der Veröffentlichung:: 16.04.2008
PPN:: 562004718
Sprache:: Englisch
Ressourcentyp:: Text
Schlagwörter:: domination; independence; inverse domination
Klassifikation:: Klasse A
Klassifikation:: für Harvesting bereitgestellt
DDC-Sachgruppe der DNB:: 510 Mathematik
Einrichtung:: Technische Universität Ilmenau, Fakultät für Mathematik und Naturwissenschaften

Zitieren

Zitierform:

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

Zitier-Link kopieren

Zugriffsstatistik

Gesamt:

Volltextzugriffe:

Metadatenansicht:

12 Monate:

Volltextzugriffe:

Metadatenansicht:

Grafik öffnen

Rechte

Export

BibTeX, MODS, MARCXML, RIS, ISI, PICA, CSV, DC