Exact and efficient generation of geometric random variates and random graphs

DOI10.1007/978-3-642-39206-1_23MaRDI QIDQ5326567zbMATH OpenOpenAlexFDO

Authors Karl Bringmann, Tobias Friedrich

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-39206-1_23

zbMATH Keywords

Erdős-Rényi random graphsRAM model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Sampling geometric inhomogeneous random graphs in linear time
• Generating Random Regular Graphs Quickly
• Geometric inhomogeneous random graphs
• A sequential algorithm for generating random graphs
• Computer generation of hypergeometric random variates†

Cited in

(12)

• Geometric inhomogeneous random graphs
• Efficient sampling methods for discrete distributions
• Generating Random Hyperbolic Graphs in Subquadratic Time
• Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory
• Sampling geometric inhomogeneous random graphs in linear time
• Learning random points from geometric graphs or orderings
• Exact sublinear binomial sampling
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• Compressed spectral screening for large-scale differential correlation analysis with application in selecting glioblastoma gene modules
• The cost of randomness in evolutionary algorithms: crossover can save random bits
• Negative-weight single-source shortest paths in near-linear time
• A linear-time \(n^{0.4}\)-approximation for longest common subsequence

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: Exact and efficient generation of geometric random variates and random graphs

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