Das graphentheoretische Dominanzproblem als stetiges Optimierungsproblem

Abstract zur Dissertation Autor: Anja Pruchnewski Titel: Das graphentheoretische Dominanzproblem als stetiges Optimierungsproblem --------------------------------------------------------------- By the domination problem we understand the problem to determine the domination number of a graph. The corresponding decision problem is NP-complete. Therefore, finding good upper bounds for the domination number is as interesting as finding algorithms (as efficient as possible) giving a dominating set, whose cardinality holds this bound. In this paper by means of the probabilistic method we give continuous formulations of the optimization problems to determine the domination number, the vector domination number, the total domination number, the total vector domination number, the covering number, and the independence number, respectively. Out of this there were developed methods to find upper bounds for the domination numbers of all concepts investigated. We present algorithms that for a given bound return a set of vertices with cardinality not greater than this bound and being dominating in the corresponding sense. Those algorithms work in polynomial time for domination and total domination, in case of bounded maximum degree even for vector domination and total vector domination. To ease solving the continous optimization problems we reduce the optimization area. That yields explicitly computable bounds for the domination number in bipartite graphs in terms of order and minimum degrees of the partition classes. These bounds are better than the bounds known from literature. For not necessarily bipartite graphs we get new upper bounds as well by considering generalized bipartitions. This approach enables us to take additional graph parameters into consideration.

Unter dem Dominanzproblem verstehen wir die Bestimmung der Dominanzzahl eines Graphen. Das zugehörige Entscheidungsproblem ist NP-vollständig. Somit ist man sowohl an guten oberen Schranken für die Dominanzzahl als auch an (möglichst effizienten) Algorithmen interessiert, die eine dominierende Menge liefern, deren Kardinalität diese Schrankenicht übersteigt. In dieser Arbeit gelingt es, mit Mitteln der wahrscheinlichkeitstheoretischen Methode stetige Optimierungsprobleme für die Dominanzzahl, die Vektordominanzzahl, die totale Dominanzzahl bzw. die totale Vektordominanzzahl sowie die Überdeckungszahl (und damit auch für die Unabhängigkeitszahl) aufzustellen. Davon ausgehend werden Methoden zur Gewinnung oberer Schranken für die Dominanzzahlen der untersuchten Konzepte angegeben. Es werden Algorithmen vorgestellt, die für eine vorgegebene Schranke eine Knotenmenge berechnen, deren Kardinalität diese Schranke nicht übersteigt und die im entsprechenden Sinn dominierend ist. Die Algorithmen erweisen sich als polynomial für die Dominanz und die totale Dominanz, im Falle beschränkter Maximalvalenz auch für die Vektordominanz und die totaleVektordominanz. Eine geeignete Einschränkung des zulässigen Bereiches liefert für paare Graphen explizit berechenbare Schranken in Abhängigkeit von den Minimalvalenzen in den Partitionsklassen. Diese Schranken sind gegenüber den aus der Literatur bekannten Schranken verbessert. Die Betrachtung verallgemeinerter Bipartitionen für nicht notwendig paare Graphen ermöglicht ebenfalls die Berechnung verbesserter Schranken und zudem die Berücksichtigung weiterer Graphenparameter bei der Schrankenberechnung.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.