Abstrakt. En dominerande uppsättning D i en graf är en delmängd av dess vertex uppsättning sådan att varje vertex är antingen i D eller har en granne i D. I detta papper är vi intresserade av uppräkning av (integrationsmässigt) minimala dominerande uppsättningar i grafer, som kallas Dom-Enum problem. Det är väl känt att detta problem kan polynomiskt reduceras till Trans-Enum problem i hypergrafer, d.v.s. problemet med att räkna upp alla minimala transversaler i en hypergraf. För det första visar vi att Trans-Enum-problemet kan reduceras polynomiskt till Dom-Enum-problemet. Som en följd finns det en output-polynom tid algoritm för Trans-Enum problem om och endast om det finns en för Dom-Enum problem. För det andra studerar vi problemet Dom-Enum i vissa grafklasser. Vi ger en output-polynom tid algoritm för Dom-Enum problem i split grafer, och införa slutförandet av en graf för att få en output-polynom tid algoritm för Dom-Enum problem i P 6 -fria ackord diagram, en riktig superklass av split grafer. Slutligen undersöker vi komplexiteten i uppräkningen av (inclusion-wise) minimala anslutna dominerande uppsättningar och minimala totala dominerande uppsättningar grafer. Vi visar att det finns en output-polynom tid algoritm för Dom-Enum problem (eller motsvarande Trans-Enum problem) om och endast om det finns en för följande uppräkning problem: minimal total dominerande uppsättningar, minimal total dominerande uppsättningar i split grafer, minimal ansluten dominerande uppsättningar i split grafer, minimal dominerande uppsättningar i co-bipartite grafer.
Dessutom ges en linjär tidsalgoritm för splitgrafer i REF när X, Y är en partition av klickdelen.
On the Enumeration of Minimal Dominating Sets and Related Notions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}