Lexikografisk bredd första sökning

Lexikografisk bredd - första sökning ( LBFS eller Lex-BFS ) är en algoritm för att ordna grafens hörn .  Algoritmen skiljer sig från bredd-först sökalgoritmen och ger en mer ordnad[ okänd term ] en sekvens av hörn i en graf.

Den lexikografiska bredd-första sökalgoritmen är baserad på idén om subsetting och utvecklades först av Rose, Tarjan och Luker (1976). En mer detaljerad genomgång av ämnet har tillhandahållits av Corneil (2004) [1] . Lexikografisk bredd-först-sökning används som en del av andra grafiska algoritmer, t.ex. ackordsgrafigenkänning , helt delad graffärgning .

Beskrivning av algoritmen

För att algoritmen ska fungera är det nödvändigt att specificera grafens vertex, från vilken korsningen börjar. Beskrivningen av algoritmen är som följer:

• Initiera en sekvens av vertexuppsättningar Σ som består av en uppsättning som innehåller alla hörn i grafen.
• Initiera en tom utgångssekvens av hörn.
• Så länge Σ inte är tom:
  • Ta en vertex v från den första mängden i Σ och ta bort den från mängden.
  • Om den första uppsättningen i Σ blir tom, ta bort den från Σ .
  • Lägg till v i slutet av utgångspunktsekvensen.
  • För varje vw- kant :
    • Definiera en mängd S i Σ som innehåller w .
    • Om uppsättning S ännu inte har delats upp vid bearbetning av v , skapa en ny tom uppsättning T och placera den före S i Σ.
    • Flytta vertex w från S till T och, om S är tomt, ta bort det från Σ.

Varje vertex bearbetas en gång, varje kant testas endast när dess två hörn bearbetas, och (om man antar att bearbetningen av operationer i en sekvens av uppsättningar Σ tar ändlig tid) tar varje iteration av den inre slingan ändlig tid. Såväl som för algoritmerna för djup - först- sökning och bredd-först-sökning, är tidskomplexiteten för algoritmen linjär och är .

Algoritmen kallas lexikografisk bredd-först-sökning eftersom den resulterande ordningen liknar resultatet av bredd-först-sökningsalgoritmen , men dessutom sorteras raderna och kolumnerna i närliggande matris i lexikografisk ordning .

Applikation

Den lexikografiska bredd-första sökalgoritmen används för att känna igen ackordsgrafer , färgar helt separerbara grafer . För att känna igen enstaka intervall- och intervallgrafer används flerhoppsalgoritmer (den lexikografiska bredd-först-sökalgoritmen med variationer används flera gånger).

Anteckningar

1. ↑ Corneil (2004) .

Litteratur

• Brandstädt, Andreas ; Le, Van Bang & Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X  .
• Bretscher, Anna; Corneil, Derek ; Habib, Michel & Paul, Christophe (2008), A simple linear time LexBFS cograph recognition algorithm , SIAM Journal on Discrete Mathematics vol 22(4): 1277–1296, doi : 10.1137/060664690 , < a http://www.liaf .jussieu.fr/~habib/Documents/cograph.ps >  .
• Corneil, Derek G. (2004), Lexicographic Breadth first search – a survey , Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Tyskland, 21-23 juni 2004, Revised Papers , vol. 3353, Lecture Notes in Computer Science, Springer-Verlag, sid. 1–19 , DOI 10.1007/978-3-540-30559-0_1  .
• Habib, Michel; McConnell, Ross; Paul, Christophe & Viennot, Laurent (2000), Lex-BFS och förfining av partitioner, med tillämpningar för transitiv orientering, intervallgrafigenkänning och konsekutiva tester , Theoretical Computer Science vol. 234 (1–2): 59–84, doi : 10.1016/S0304-3975(97)00241-7 , < http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf > . Hämtad 7 juni 2016. Arkiverad 26 juli 2011 på Wayback Machine . 
• Rose, DJ; Tarjan, RE & Lueker, GS (1976), Algorithmic aspects of vertex elimination on graphs , SIAM Journal on Computing vol. 5 (2): 266–283 , DOI 10.1137/0205021  .