Efficient domination and polarity Nevries, Ragnar Christopher , 1984- Text theses Text Hochschulschrift 2014 2014 eng electronic resourceremoteComputermedienOnline-Ressourcetext/htmlapplication/pdfOnline-Ressource graph. Darst. 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. vorgelegt von Ragnar Christopher Nevries Rostock, Univ., Fak. für Informatik und Elektrotechnik, Diss., 2014 004.015115 004 510 ST 134 31.12 http://rosdok.uni-rostock.de/resolve?urn=urn:nbn:de:gbv:28-diss2014-0183-3 http://rosdok.uni-rostock.de/resolve?urn=urn:nbn:de:gbv:28-diss2014-0183-3&pdf http://nbn-resolving.de/urn:nbn:de:gbv:28-diss2014-0183-3 Efficient domination and polarity--(DE-627)799223662 urn:nbn:de:gbv:28-diss2014-0183-3 oclc: 935760063 ppn: (DE-627)806818689