Vi anser att problemet med provtagning en kant nästan enhetligt från en okänd graf, G = (V, E). Tillgång till grafen ges via frågor av följande typer: (1) enhetliga vertex frågor, (2) grad frågor, och (3) grannar frågor. Vi beskriver en algoritm som returnerar en slumpmässig e-kant med hjälp av Õ(n/ εm) frågor i förväntan, där n =  på V är antalet hörn, och m =  på E är antalet kanter, så att varje kant e provtas med sannolikhet (1 ± ε) / m. Vi bevisar att vår algoritm är optimal i den meningen att alla algoritmer som tar prov på en kant från en nästan enhetlig distribution måste utföra frågor om.
Det relaterade problemet med provtagningskanter från en nästan enhetlig distribution studerades nyligen av Eden och Rosenbaum i REF.
On Sampling Edges Almost Uniformly
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}