Dissociationsnummer

Exempel för definition av dissociationsnumret

I den matematiska disciplinen grafteori kallas en delmängd av hörn i en graf G dissociation om den inducerar en subgraf med maximal grad 1. Antalet hörn i en maximal kardinalitetsdissociationsmängd i G kallas dissociationstalet G , betecknat av diss( G ). Problemet med att beräkna diss( G ) (dissociationsnummerproblem) studerades först av Yannakakis . Problemet är NP-hårt även i klassen av tvådelade och plana grafer .

En algoritm för att beräkna en 4/3-approximation av dissociationstalet i tvådelade grafer publicerades 2022.

Dissociationstalet är ett specialfall av det mer allmänna Maximum k-beroende Set Problem för $k=1$ . Problemet frågar efter storleken på en största delmängd $S$ av hörnen på en graf $G$ , så att den inducerade subgrafen $G[S]$ har maximal grad $k$ .

Anteckningar

• Yannakakis, Mihalis (1981). "Problem med att radera nod på tvådelade grafer". SIAM J. Comput . 10 (2): 310–327. doi : 10.1137/0210022 .
• Papadimitriou, Christos H.; Yannakakis, Mihalis (1982). "Komplexiteten i problem med begränsade spännträd". J. ACM . 29 (2): 285–309. doi : 10.1145/322307.322309 .
• Hosseinian, Seyedmohammadhossein; Butenko, Sergiy (2022). "En förbättrad approximation för maximal k-beroende uppsättning på tvådelade grafer". Diskret Appl. Matematik . 307 : 95–101. arXiv : 2110.02487 . doi : 10.1016/j.dam.2021.10.015 .