Zur Seitennavigation oder mit Tastenkombination für den
accesskey
-Taste und Taste 1
Zum Seiteninhalt oder mit Tastenkombination für den
accesskey
und Taste 2
S
tartseite
A
nmelden
Sommer 2024
Hilfe
Sitemap
Impressum
Datenschutz
node2
Studentisches Leben
Veranstaltungen
Einrichtungen
Räume und Gebäude
Personen
Forschung
Startseite
Publikation: Dissertationsschrift
Efficient domination and polarity
Grunddaten
Abstract
Autoren
Einrichtung
Grunddaten
Titel
Efficient domination and polarity
Erscheinungsjahr
2014
Publikationsform
Elektronische Ressource
Publikationsart
Dissertationsschrift
Sprache
Englisch
Letzte Änderung
29.11.2014 02:13:35
Bearbeitungsstatus
durch UB Rostock abschließend validiert
Dauerhafte URL
http://purl.uni-rostock.de/fodb/pub/46428
Links zu Katalogen
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.
Autor
Nevries, Ragnar
Einrichtung
IEF/Bereich Informatik