Abstrakt. Vi anser att problemet med minsta spännvidd i en miljö där information om kantvikterna i den givna grafen är osäker. Inledningsvis, för varje kant e av grafen bara en uppsättning Ae, som kallas ett osäkerhetsområde, som innehåller den faktiska kantvikt vi är kända. Algoritmen kan "uppdatera" e för att få den kantvikt vi  på Ae. Uppgiften är att mata ut kantuppsättningen av ett minsta spännträd efter ett minsta antal uppdateringar. En algoritm är k-update konkurrenskraftig om den gör som mest k gånger så många uppdateringar som den optimala. Vi presenterar en 2-uppdaterings konkurrerande algoritm om alla områden Ae är öppna eller triviala, vilket är det bästa möjliga bland deterministiska algoritmer. Villkoret på områdena Ae är att utesluta degenererade ingångar för vilka ingen konstant uppdatering konkurrenskraftig algoritm kan existera. Därefter överväger vi en inställning där grafens hörn motsvarar punkter i Euclidean utrymme och vikten av en kant är lika med avståndet av dess endpoints. Platsen för varje punkt anges inledningsvis som ett osäkerhetsområde, och en uppdatering avslöjar den exakta platsen för punkten. Vi ger en allmän relation mellan kanten osäkerhet och vertex osäkerhet versioner av ett problem och använda den för att härleda en 4-uppdatering konkurrenskraftig algoritm för minsta spännvidd träd problem i vertex osäkerhet modell. Återigen visar vi att detta är bästa möjliga bland deterministiska algoritmer. Algoritmer och datastrukturer; Aktuella utmaningar: mobil och nätbaserad databehandling. En del av den framlagda forskningen genomfördes medan den andra och femte författaren var studieledig från universitetet i Leicester och den andra författaren besökte University of Queensland. Författarna vill tacka dessa institutioner för deras stöd.
I REF, författarna anser den minsta spännvidd träd problem med osäkerhet och föreslå en algoritm med frågeförhållande 2.
Computing Minimum Spanning Trees with Uncertainty
{'venue': 'Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008)', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}