zum Inhalt

 

Nevries,  Ragnar

Efficient domination and polarity

Rostock : Universität , 2014

https://doi.org/10.18453/rosdok_id00001431

http://purl.uni-rostock.de/rosdok/id00001431

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.

Dissertation Open Access


Einrichtung :
Fakultät für Informatik und Elektrotechnik
Gutachter :
Brandstädt,  Andreas  (Prof. Dr.)
Widmayer,  Peter  (Prof. Dr.)
Huang,  Jing  (Prof. Dr.)
Jahr der Abgabe:
2014
Jahr der Verteidigung:
2014
Sprache(n) :
Englisch
Schlagworte:
efficient algorithms, NP-completeness, monopolarity, efficient edge domination
DDC Klassifikation :
004 Informatik
URN :
urn:nbn:de:gbv:28-diss2014-0183-3
Persistente URL:
http://purl.uni-rostock.de/rosdok/id00001431
erstellt am:
2014-11-11
zuletzt geändert am:
2018-06-30
Volltext