Bron-Kerbosh algoritm

Bron-Kerbosh-algoritmen  är en gren-och-bunden metod för att hitta alla klicker (liksom maximala oberoende uppsättningar av hörn ) i en oriktad graf . Utvecklad av de holländska matematikerna Bron och Kerbosch 1973, är den fortfarande en av de mest effektiva klicksökningsalgoritmerna.

Algoritm

Algoritmen använder det faktum att varje klick i en graf är dess inklusionsmaximala kompletta subgraf . Med utgångspunkt från ett enda hörn (som bildar en komplett subgraf), försöker algoritmen vid varje steg att öka den redan konstruerade kompletta subgrafen genom att lägga till hörn från uppsättningen av kandidater till den. Hög hastighet säkerställs genom att skära av när man itererar över alternativ som inte leder till konstruktionen av en klick, för vilken en extra uppsättning används, där hörn placeras som redan har använts för att öka hela subgrafen.

Algoritmen fungerar på tre uppsättningar av grafhörn:

  1. Uppsättningssammansättningen  är uppsättningen som vid varje steg av rekursionen innehåller hela subgrafen för det givna steget . Det bygger rekursivt.
  2. Uppsättningen av kandidater  är uppsättningen av hörn som kan öka compsub
  3. Not set  är uppsättningen av hörn som redan har använts för att expandera compsub i de tidigare stegen i algoritmen.

Algoritmen är en rekursiv procedur som tillämpas på dessa tre uppsättningar.

PROCEDUR förlängning ( kandidater , inte ) : OM inte kandidater är tomma OCH inte INNEHÅLLER EN VERTEX ANSLUTEN TILL ALLA hörn från kandidater , UTFÖR : 1 Välj vertex v från kandidater och lägg till det i compsub 2 Form new_candidates och new_not , ta bort från kandidater och inte hörn som inte är ansluten till v 3 OM new_candidates och new_not är tomma 4 TO compsub - klick 5 ELSE anrop förlänga rekursivt ( new_candidates , new_not ) 6 Ta bort v från compsub och kandidater och lägg in inte

Variationer

Hitta maximala (med avseende på inkludering) oberoende uppsättningar av hörn

Det är lätt att se att klickproblemet och det oberoende uppsättningsproblemet i huvudsak är likvärdiga: var och en av dem erhålls från den andra genom att konstruera ett grafkomplement  - en graf som innehåller alla hörn i den ursprungliga grafen, och i grafens komplement hörn är sammankopplade med en kant om och endast om de inte var sammankopplade i den ursprungliga grafen.

Därför kan Bron-Kerbosch-algoritmen användas för att hitta de maximala inklusionsoberoende uppsättningarna av hörn genom att konstruera ett tillägg till den ursprungliga grafen, eller genom att ändra villkoret i huvudslingan (stoppvillkor) och bilda nya uppsättningar new_candidates och new_not :

  1. Villkor i huvudslingan: får inte innehålla någon vertex som INTE är ansluten till NÅGON av hörnen i uppsättningen av kandidater
  2. För att bilda nya_kandidater och ny_inte måste du ta bort från kandidater och inte de hörn som är ANSLUTNA till det valda hörnet.

Beräkningskomplexitet

Linjär med avseende på antalet klick i diagrammet. Tomita, Tanaka och Haruhisa 2006 visade att den värsta algoritmen körs i O ( 3n /3 ), där n är antalet hörn i grafen.

Se även

Litteratur