ISBN 9783843958103

978-3-8439-5810-3, Reihe Mathematik

Christoph Geis
Covering and domination problems on graphs

198 Seiten, Dissertation Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau (2026), Hardcover, A5

Zusammenfassung / Abstract

Abdeckungs- und Dominierungsprobleme sind eine klassische Familie von Optimierungsproblemen, die dem selben Schema folgen: Gegeben ist ein Graph G zusammen mit einer Menge von Konsumenten und einer Menge von Versorgen, gesucht ist eine Menge von Versorgern mit minimaler Größe (oder Gewicht), die alle Konsumenten versorgen.

In der ersten Hälfte dieser Dissertation definieren wir das Problem Preselected Subgraph Multicover (PSMC).

Eine Instanz (G,S,c,d,u) dieses Problems besteht aus einem einfachen ungerichteten Graphen G mit einer Bedarfsfunktion d, einer Menge S von Teilgraphen von G mit Kosten c und Kapazitäten u.

Eine zulässige Lösung ist eine Multimenge über S, welche jeden vorausgewählten Graphen H in S höchstens u(H) mal enthält, und jeden Knoten v in G mit mindestens d(v) vorausgewählten Teilgraphen abdeckt. Eine optimale Lösung ist eine zulässige Lösung mit minimalem Gewicht bezüglich c.

Wir zeigen, dass PSMC zahlreiche bekannte Probleme wie Dominating Set, Vertex Cover und Edge Cover verallgemeinert. Wir beschreiben die Komplexität von PSMC auf einfachen Graphklassen wie Wegen, Kreisen und Sterngraphen. Zudem betrachten wir PSMC eingeschränkt auf Instanzen (G,S,c,d,u) bei denen G ein Baum ist, dessen Knoten höchstens Bedarf k haben; und S nur Wege enthält, welche außerdem höchstens Länge l haben. Wir zeigen, dass PSMC für kleine Werte für k und l in Polynomialzeit lösbar ist, für größere Werte jedoch NP-schwer ist.

Darüber hinaus betrachten wir PSMC eingeschränkt auf Instanzen (G,S,c,d,u), bei denen die zyklomatische Zahl von G beschränkt ist, und die maximale Anzahl von Blättern jedes einzelnen Graphen in S auch beschränkt ist. Wir konstruieren zwei Approximationsalgorithmen für dieses Problem.

Die zweiten Hälfte dieser Arbeit betrachtet Varianten einiger klassischer Abdeckungs- und Dominierungsprobleme, darunter das Gruppensteinerbaumproblem, das p-Center Problem und dass Problem, eine dominierende Menge auf zwei Wegen zu finden.