Sammanfattning Vi visar med stor sannolikhet att en skippa graf innehåller en 4-regelbunden expander som en subgraf och uppskattar kvaliteten på expansionen via simuleringar. Som en följd av detta, hoppa grafer innehåller en stor ansluten komponent även efter en kontradiktorisk radering av noder. Vi visar hur expansionsfastigheten kan användas för att provsmaka en nod i skip-grafen på ett mycket effektivt sätt. Vi visar också att expansionsfastigheten kan användas för att ladda balans hoppa grafen snabbt. Slutligen visas att skip-grafen kan fungera som ett ostrukturerat P2P-system, vilket gör det till en bra kandidat för ett hybrid P2P-system.
Det visades i REF att hoppa grafer innehåller expanders som subgraphs w.h.p., som kan användas som en randomiserad expander konstruktion.
The expansion and mixing time of skip graphs with applications
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Engineering']}