Textdokument
Die Struktur dominierender Mengen in Graphen
Lade...
Volltext URI
Dokumententyp
Dateien
Zusatzinformation
Datum
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
Ein zentrales Konzept in der Graphentheorie ist das der Dominierung. Eine dominierende Menge eines Graphen G ist eine Teilmenge X der Knoten, für die jeder Knoten aus V (G) \ X einen Nachbarn in X besitzt. Anschaulich formuliert, eine dominierende Menge in einem Netzwerk ist ein Komitee, bei dem gilt, dass jedes Nicht-Mitglied ein Mitglied kennt. Dominierende Mengen, ihre Anwendungen und Varianten sind in der Forschungsliteratur sehr gut untersucht.
In dieser Arbeit tragen wir grundlegende Untersuchungen zu den strukturellen und algorithmischen Eigenschaften dominierender Mengen bei. Im Mittelpunkt stehen dabei spezielle dominierende Mengen, deren induzierte Teilgraphen zusätzlichen strukturellen Bedingungen genügen.