Key points are not available for this paper at this time.
Zusammenfassung Die totale Dominanz und das offene Packen bilden ein primales-duales Paar von Problemen. Eine Mengenauswahl S eines Graphen G wird als offenes Packen in G bezeichnet, wenn kein Paar von verschiedenen Vertices in S einen gemeinsamen Nachbarn in G hat. Die Kardinalität eines maximalen offenen Packens in G wird als die offene Packungszahl, ρᵒ(G), von G bezeichnet, die eine untere Schranke für die totale Dominanzzahl von G ist. Gegeben ist ein Graph G und eine positive ganze Zahl k. Das Problem OFFENES PACKEN prüft, ob G ein offenes Packen der Größe mindestens k besitzt. Es ist bekannt, dass OFFENES PACKEN für Split-Graphen (und somit für kordale Graphen) NP-vollständig ist, Ramos et al., 2014. In dieser Arbeit verwenden wir einen dynamischen Programmierungsansatz, um zu zeigen, dass ein maximales offenes Packen in Intervallgraphen (eine Unterklasse der kordalen Graphen) in O(n³) Zeit gefunden werden kann.
Shalu et al. (Fr,) haben diese Frage untersucht.