Vi studerar fastighetstestalgoritmer i riktade grafer (digrafer) med maximal ingrad och maximal utgrad övre gräns d. För riktade grafer med begränsad grad finns det två olika modeller i fastighetstestning introducerade av Bender och Ron (2002). I den dubbelriktade modellen kan man komma åt både inkommande och utgående kanter medan man i den enkelriktade modellen endast kan komma åt utgående kanter. I vårt papper ger vi en ny relation mellan de två modellerna: vi bevisar att om en fastighet kan testas med konstant frågekomplex i den dubbelriktade modellen, då kan den testas med sublinjär frågekomplexitet i den enkelriktade modellen. En följd av detta resultat är att i den enkelriktade modellen (modellen som tillåter endast frågor till de utgående grannarna), varje egenskap i hyperfinita digraphs är testabar med sublinjär fråge komplexitet.
Mer nyligen, Czumaj et al. har visat att om en egenskap kan testas med konstant frågekomplex i den dubbelriktade inställningen, kan den testas med sublinjär frågekomplexitet i den enkelriktade modellen REF.
Relating two property testing models for bounded degree directed graphs
{'venue': 'STOC 2016', 'journal': None, 'mag_field_of_study': ['Computer Science']}