%0 Book
%T Efficient domination and polarity
%A Nevries, Ragnar Christopher
%D 2014
%G English
%F 806818689
%O vorgelegt von Ragnar Christopher Nevries
%O Rostock, Univ., Fak. für Informatik und Elektrotechnik, Diss., 2014
%X 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.
%L 004.015115
%9 theses
%9 Text
%9 Hochschulschrift
%U http://rosdok.uni-rostock.de/resolve?urn=urn:nbn:de:gbv:28-diss2014-0183-3
%U http://rosdok.uni-rostock.de/resolve?urn=urn:nbn:de:gbv:28-diss2014-0183-3&pdf
%U http://nbn-resolving.de/urn:nbn:de:gbv:28-diss2014-0183-3