Titel: |
Efficient domination and polarity |
|
Beteiligte Personen: |
Ragnar Nevries[VerfasserIn] |
 |
1060577844 |
Andreas Brandstädt
, Prof. Dr.[AkademischeR BetreuerIn] |
 |
133631737 |
|
Universität Rostock, Institut für Informatik |
Peter Widmayer
, Prof. Dr.[AkademischeR BetreuerIn] |
 |
12915122X |
|
ETH Zürich, Institut für Theoretische Informatik |
Jing Huang
, Prof. Dr.[AkademischeR BetreuerIn] |
 |
138539391 |
|
University of Victoria, Mathematics and Statistics |
|
Beteiligte Körperschaften: |
Universität Rostock, Fakultät für Informatik und Elektrotechnik[Grad-verleihende Institution] |
 |
10085032-7 |
|
|
Zusammenfassung: |
The thesis considers the following graph problems:
Efficient (Edge) Domination seeks for an independent vertex (edge) subset D such that
all other vertices (edges) have exactly one neighbor in D. Polarity asks for a vertex
subset that induces a complete multipartite graph and that contains a vertex of every
induced P_3. Monopolarity is the special case of Polarity where the wanted vertex
subset has to be independent. These problems are NP-complete in general, but efficiently
solvable on various graph classes.
The thesis sharpens known NP-completeness results and presents new solvable cases.
[Englisch] |
|
Dokumenttyp: |
|
Einrichtung: |
Fakultät für Informatik und Elektrotechnik |
|
Sprache: |
|
Sachgruppe der DNB: |
|
|
Veröffentlichung / Entstehung: |
Rostock
Rostock: Universität Rostock
|
2014
|
|
|
Identifikatoren: |
|
|
Zugang: |
frei zugänglich (Open Access)
|
|
Lizenz/Rechtehinweis: |
alle Rechte vorbehalten Das Werk darf ausschließlich nach den vom deutschen Urheberrechtsgesetz festgelegten Bedingungen genutzt werden. |
|
|
RosDok-ID: |
rosdok_disshab_0000001252 |
erstellt / geändert am: |
11.11.2014 / 08.08.2023
|
Metadaten-Lizenz: |
Die Metadaten zu diesem Dokument sind gemeinfrei (CC0 1.0 Universal Public Domain Dedication). |