This thesis investigates root finding, that is finding the first vertex, of a type of random graph, the l−dags or random recursive dags, when we add an additional Erdős-Rényi graph on the same vertex set, which represents noise. The findings show that the structure of double cycles which works for the l−dags without noise is robust to considerable noise levels. We then also explore numerically root finding algorithms for uniform attachment trees with noise, which is a current open question in the field, in order to provide some insight into future lines of research.

Denna avhandling undersöker rotfinnande, det vill säga att hitta den första noden, av en typ av slumpmässig graf, l−dags eller slumpmässiga rekursiva dags, när vi lägger tillen ytterligare Erdős-Rényi-graf på samma noduppsättning, vilket representerar brus. Resultaten visar att strukturen av dubbla cykler som fungerar för ℓ−dags utan brus är robusta mot betydande brusnivåer. Vi utforskar sedan även numeriskt rotfinnande algoritmer för uniform attachment trees och brus, vilket är en aktuell öppen fråga inom området, för att ge en inblick i framtida forskningslinjer.