Algorithmische Ergebnisse für das Problem der schwachen römischen Dominanz in Graphen

Betrachten Sie einen Graphen G = (V, E) und eine Funktion f: V \0, 1, 2\. Ein Scheitelpunkt u mit f (u) = 0 wird als von f undefended definiert, wenn er keine Nachbarschaft zu einem Scheitelpunkt mit einem positiven f-Wert hat. Die Funktion f wird als schwache römische Dominierende Funktion (WRD-Funktion) bezeichnet, wenn für jeden Scheitelpunkt u mit f (u) = 0 es einen Nachbarn v von u mit f (v) > 0 gibt und eine neue Funktion f': V \0, 1, 2\, die wie folgt definiert ist: f' (u) = 1, f' (v) = f (v) - 1 und f' (w) = f (w), für alle Scheitelpunkte w in V\u, v\; so dass keine Scheitelpunkte von f' undefended sind. Das Gesamtgewicht von f entspricht ₕ ₕ f (v) und wird als w (f) bezeichnet. Die schwache römische Dominationsnummer, bezeichnet durch ᵣ (G), stellt min\w (f) dar ~~f ist eine WRD-Funktion von G\. Für einen gegebenen Graph G wird das Problem, eine WRD-Funktion mit Gewicht ᵣ (G) zu finden, als Problem der minimalen schwachen römischen Dominanz definiert. Es ist bereits bekannt, dass dieses Problem NP-schwer für bipartite und chordale Graphen ist. In diesem Papier untersuchen wir weiter die algorithmische Komplexität des Problems. Wir beweisen die NP-Härte des Problems für sternkonvexe bipartite Graphen und kammkonvexe bipartite Graphen, die Unterklassen der bipartiten Graphen sind. Darüber hinaus zeigen wir, dass das Problem für die begrenzte Grad sternkonvexen bipartiten Graphen effizient lösbar ist. Wir beweisen auch die NP-Härte des Problems für Split-Graphen, eine Unterklasse der chordalen Graphen. Positiv zu vermerken ist, dass wir polynomielle Algorithmen zur Lösung des Problems für P₄-dünne Graphen präsentieren. Darüber hinaus haben wir einige Näherungsergebnisse vorgestellt.