TY  - BOOK
AU  - Nevries, Ragnar Christopher
PY  - 2014
DA  - 2014//
TI  - Efficient domination and polarity
AB  - 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.
UR  - http://rosdok.uni-rostock.de/resolve?urn=urn:nbn:de:gbv:28-diss2014-0183-3
UR  - http://rosdok.uni-rostock.de/resolve?urn=urn:nbn:de:gbv:28-diss2014-0183-3&pdf
UR  - http://nbn-resolving.de/urn:nbn:de:gbv:28-diss2014-0183-3
LA  - English
N1  - vorgelegt von Ragnar Christopher Nevries
ID  - 806818689
ER  -