Logo des Repositoriums
 
Textdokument

Die Struktur dominierender Mengen in Graphen

Vorschaubild nicht verfügbar

Volltext URI

Dokumententyp

Zusatzinformation

Datum

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.

Beschreibung

Schaudt, Oliver (undefined): Die Struktur dominierender Mengen in Graphen. Ausgezeichnete Informatikdissertationen 2011. Bonn: Gesellschaft für Informatik. PISSN: 1617-5468. ISBN: 978-3-88579-416-5. pp. 171-180

Schlagwörter

Zitierform

DOI

Tags