Sublinear Random Access Generators for Preferential Attachment Graphs

DOI10.1145/3464958OpenAlexW2963965835MaRDI QIDQ5035872FDOQ5035872

Authors: Guy Even, Reut Levi, Moti Medina, Adi Rosén 

Publication date: 22 February 2022

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7424/

Recommendations

• Sublinear Random Access Generators for Preferential Attachment Graphs.
• Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory
• Sublinear graph approximation algorithms
• Sublinear-time algorithms for approximating graph parameters
• Generating Random Hyperbolic Graphs in Subquadratic Time
• scientific article; zbMATH DE number 3943865
• scientific article; zbMATH DE number 2019628
• Hard graphs for randomized subgraph exclusion algorithms
• Efficient and near-optimal algorithms for sampling connected subgraphs
• Subgraphs in preferential attachment models

zbMATH Keywords

sublinear algorithmslocal computation algorithmsrandom graph generatorpreferential attachment graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cited In (2)

• Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory
• Parallel and I/O-efficient algorithms for non-linear preferential attachment

This page was built for publication: Sublinear Random Access Generators for Preferential Attachment Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5035872)