Maximum Independent Set Algorithmus
Glaube ich nicht, es existiert ein Algorithmus für das finden der maximalen unabhängigen vertex-set in einem der bipartite graph andere als die brute-force-Methode zu finden, die maximal unter allen möglichen unabhängigen Sätzen.
Frage ich mich, über den pseudocode zum finden aller möglichen vertex sets.
Sagen gegeben, einen zweiseitigen Graphen mit 4 blauen Ecken und 4 rot. Aktuell würde ich
Start with an arbitrary blue,
find all red that don't match this blue
put all these red in Independent Set
find all blue that dont match these red
put these blue in Independent Set
Repeat for next vertex in blue
Repeat all over again for all blue then all vertices in red.
Verstehe ich, dass dieser Weg nicht mir alle möglichen Unabhängigen Satz-Kombinationen an alle, da nach dem ersten Schritt ich bin der Wahl alle von der nächsten Farbe vertices, die nicht passen, anstatt Schritt durch jede Möglichkeit.
Beispielsweise gegeben ein graph mit den passenden
B R
1 1
1 3
2 1
2 3
3 1
3 3
4 2
4 4
Start with blue 1
Choose red 2 and 4 since they dont match
Add 2, 4 to independent Set
Choose 2 and 3 from blue since they dont with 2 or 4 from red
Add 2 and 3 from blue to independent set as well.
Independent Set = 1,2,3 from blue 2,4 from red
Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set)
Gibt es eine Möglichkeit, kann ich die Verbesserung dieses Algorithmus, um bessere Suche für alle Möglichkeiten. Ich weiß, dass ein | - Maximum-Satz für einen zweiseitigen Graphen| = |Rot| + | - Blau| - |Maximum Matching|.
Entsteht das problem, mit der Möglichkeit, dass durch die Wahl aller möglichen rot in der ersten gehen für ein bestimmtes blau, wenn die roten eine Verbindung zu allen anderen möglichen blau dann mein set immer nur alle 1 blau und der rest rot.
- Wie groß ist die Grafik? Anzahl der Knoten und Anzahl der Kanten? Könnte es möglich sein, zu füttern, ergänzen des Diagramms in der standard-maximal-clique Algorithmus.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Es ist: finden die maximale unabhängigen Satz ist äquivalent zur Suche nach dem minimum-vertex-cover (unter Ergänzung des Ergebnisses), und König ' s theorem Staaten, die minimum-vertex-cover in der bipartite Graphen ist äquivalent zu maximum matching, und, die, die gefunden werden können in polynomieller Zeit. Ich weiß nicht, über die Suche nach allen übereinstimmungen, aber es scheint, es kann exponentiell viele.
Aaron McDaid erwähnt in seinem inzwischen gelöschten Antwort, das problem des maximal independent set ist äquivalent zu finden, dass eine maximale clique. Die Gleichwertigkeit ist, dass die Suche nach einem maximum independent set in einem Graphen G ist der gleiche wie der Suche nach einer maximalen clique im Komplement von G. Das problem ist bekanntlich NP-vollständig.
Den brute-force-Lösung, die Sie erwähnen, dauert
O(n^2 2^n), aber Sie können tun, besser als dieser. Robson hat ein Papier mit dem Titel ""Algorithmen für maximale independent sets" von 1986, das gibt einen Algorithmus, der nimmtO(2^{c*n})für eine Konstante0<c<1(ich glaubecist um1/4, aber ich könnte falsch sein). Nichts davon ist spezifisch für eine der bipartite graph.Eine Sache zu beachten, wenn Sie eine der bipartite Graphen ist, die beiden Seiten bilden einen unabhängigen Satz. In der komplett der bipartite graph
K_{b,r}die partitioniert istB x Rmit|B|=bund|R|=rwo es eine Kante von jedem vertex inBauf jeden vertex inRund keine innerhalbBnoch keine innerhalbRmaximal independent set istBwennb>=r, sonst ist esR.Unter
BoderRnicht Arbeit im Allgemeinen. sdcvvc erwähnt das Beispiel mit den Eckpunkten{1,2,3,A,B,C}und Kanten{A,1}, {A,2}, {A,3}, {B,3}, {C,3}. In diesem Fall wird die maximale unabhängigen Satz ist{1,2,B,C}, die größer ist als entweder partition{A,B,C}oder{1,2,3}.Kann es verbessern Robson ' s Algorithmus, mit zu beginnen, die den größeren
BoderRund gehen von dort, aber ich bin mir nicht sicher wie viel Unterschied das macht.Alternativ können Sie die Hopcroft–Karp-Algorithmus auf die zweiseitige Ergänzung eines Graphen zu finden, die ein maximum matching, und nehmen Sie dann die Scheitelpunkte verwendet, die in der Abstimmung der unabhängigen Satz. Dies gibt einen polynomialzeit-Algorithmus, um das problem zu lösen.