Abstrakt. Koml os har utarbetat ett sätt att använda ett linjärt antal binära jämförelser för att testa om en given spänna träd av en graf med kant kostnader är ett minimum spänna träd. Det totala beräkningsarbete som krävs av hans metod är dock mycket större än linjärt. Vi beskriver en linjär tid algoritm för att verifiera ett minsta spanning träd. Vår algoritm kombinerar resultatet av Koml os med en förbearbetnings- och bordslook-up metod för små subproblem och med en tidigare känd nästan linjär tid algoritm. Dessutom presenterar vi en optimal deterministisk algoritm och en linjär-tids randomiserad algoritm för känslighetsanalys av minsta spännviddsträd. 1. Vad är det för fel på dig? Inledning. Anta att vi vill lösa några problem som vi i förväg vet storleken på indata, med hjälp av en algoritm från någon välrenommerad klass av algoritmer. Till exempel, överväga sortering n nummer, när n är xed i förväg, med hjälp av ett binärt jämförelseträd. Med tanke på en tillräcklig mängd förbehandlingstid och lagringsutrymme, kan vi i ett förbearbetningssteg beräkna ett minsta djupgående jämförelseträd, lagra det explicit, och sedan lösa alla fall av sorteringsproblem genom att använda det förberäknade jämförelseträdet. Denna teknik är naturligtvis i allmänhet värdelös eftersom den är oöverkomligt dyr i förbehandlingstid och lagringsutrymme, båda är åtminstone exponentiellt i n. Det finns situationer där denna idé kan användas till fördel, dock. Detta är fallet när det gäller problem som är känsliga för mycket eektiv klyfta och seger. Tanken är att dela upp problemet som ska lösas i subproblem, som kategoriseras i klasser. Om subproblemen är tillräckligt små kan de lösas eektivt enligt följande: En optimal algoritm för varje klass är förkomputerad och lagras i en uppslagstabell, och varje instans av ett subproblem löses genom att titta upp och köra algoritmen för sin klass. För att denna teknik ska betala o, måste lösa alla subproblem minska det ursprungliga problemet tillräckligt att det kan lösas snabbt med avseende på storleken på det ursprungliga problemet genom att använda en icke-optimal algoritm. I detta dokument presenteras en tillämpning av denna allmänna teknik på två problem som rör minimispannträd. Detta tillvägagångssätt föreslogs uttryckligen av Larmore [15], som använde det för att lösa ett problem med konvex matrissökning. Relaterade tekniker användes av Gabow och Tarjan [8] för att lösa ett osammanhängande fackproblem, av Harel och Tarjan [12] till ND närmaste vanliga förfäder i ett träd, och av Fredman [5] för att lösa alla par kortaste vägen problem. Vi presenterar en algoritm som veries en minsta spännvidd träd i en n-vertex, m-kant graf i O(m) tid. Vi ger också algoritmer som utför känslighetsanalys av minsta spännvidd i värsta fall minimum till inom en konstant faktor och linjär förväntad tid. Vår modell av beräkning gör det möjligt att jämföra, addera eller subtrahera kantkostnader vid enhetskostnad, och sidoberäkningar som ska utföras på en enhet kostnad slumpmässig åtkomst maskin med ordstorlek (logn) bitar. Verikationsalgoritmen använder jämförelsebandet för Koml os [14] för underproblemen och Tarjans O(m; n)-algoritm [17] för det minskade problemet. För känslighetsanalys löser vi subproblemen med hjälp av ett resultat av Goddard, King och Schulman [9] i det randomiserade fallet och uppräkning av alla möjliga algoritmer i det deterministiska fallet. I båda fallen behandlar Tarjans O(m(m; n)-tidskänslighetsanalysalgoritm [18] det minskade problemet. Vi beskriver algoritmerna i avsnitten 2 och 3. Avsnitt 4 innehåller avslutande anmärkningar. Det är viktigt att notera att vår beräkningsmodell endast tillåter mycket enkla operationer på kanten kostnader, nämligen binär jämförelse, addition, och subtraktion. I en mer kraftfull modell där lite manipulering av kanten kostnader är möjligt, bättre resultat kan uppnås med hjälp av tabell lookup och andra idéer. Framför allt visade Harel [11] att om kantkostnaderna är heltal polynomiellt avgränsade i n, sedan på en enhet-costrandom-accessmaskin den minsta spanningtree verikation och känslighetsanalys problem kan lösas deterministiskt i linjär tid. Mer nyligen Fredman och Willard [6] visade att om kanten kostnader är singel-precision heltal, då ett minimum spänna a
Med hjälp av denna anslutning, i en modell där kantvikter är atomära, men sidoberäkningar på ett RAM är tillåtna, kan alla de bästa swapkanterna hittas i O(m) förväntad tid med hjälp av en randomiserad algoritm som ges av Dixon et al. Hoppa över det.
Verification and Sensitivity Analysis Of Minimum Spanning Trees In Linear Time
{'venue': 'SIAM J. Comput', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}