| title: |
| Efficient domination and polarity |
|
| contributing persons: |
| 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 |
|
| contributing corporate bodies: |
| Universität Rostock, Fakultät für Informatik und Elektrotechnik[Grad-verleihende Institution] |
|
10085032-7 |
|
| |
| abstract: |
|
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.
[English] |
|
| document type: |
|
| institution: |
| Faculty of Computer Science and Electrical Engineering |
|
| language: |
|
| subject class (DDC): |
| 004 Data processing Computer sciences |
|
| |
publication /
production: |
Rostock
|
Rostock: Universität Rostock
|
|
2014
|
|
| |
| identifiers: |
|
| |
| access condition: |
|
| license/rights statement: |
all rights reserved
This work may only be used under the terms of the German Copyright Law (Urheberrechtsgesetz). |
|
|
| RosDok id: |
rosdok_disshab_0000001252 |
| created / modified: |
11.11.2014 / 08.08.2023
|
| metadata license: |
The metadata of this document was dedicated to the public domain
(CC0 1.0 Universal Public Domain Dedication). |
access
viewer
fulltext