| 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: 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). |
Zugang
Viewer
Volltext