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). |