A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
From MaRDI portal
Publication:4842123
DOI10.1137/S0097539793247634zbMath0831.68049OpenAlexW2004694806WikidataQ105584159 ScholiaQ105584159MaRDI QIDQ4842123
Hanno Lefmann, Richard A. Duke, Vojtěch Rödl
Publication date: 26 July 1995
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793247634
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items
Additive approximation of generalized Turán questions ⋮ Embedding graphs with bounded degree in sparse pseudorandom graphs ⋮ On characterizing hypergraph regularity ⋮ Integer and fractional packings in dense 3‐uniform hypergraphs ⋮ The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics ⋮ Ramsey properties of random hypergraphs ⋮ Bounds for graph regularity and removal lemmas ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ A Short proof of the blow-up lemma for approximate decompositions ⋮ On sufficient conditions for spanning structures in dense graphs ⋮ Perfectly packing graphs with bounded degeneracy and many leaves ⋮ Local-vs-global combinatorics ⋮ An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions ⋮ On Regularity Lemmas and their Algorithmic Applications ⋮ Minimalist designs ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Rainbow structures in locally bounded colorings of graphs ⋮ Extremal results in sparse pseudorandom graphs ⋮ A rainbow blow-up lemma for almost optimally bounded edge-colourings ⋮ A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds ⋮ Method for quickly inferring the mechanisms of large-scale complex networks based on the census of subgraph concentrations ⋮ A blow-up lemma for approximate decompositions ⋮ A sparse regular approximation lemma ⋮ Monochromatic bounded degree subgraph partitions ⋮ Maximum dispersion problem in dense graphs ⋮ Short paths in quasi-random triple systems with sparse underlying graphs ⋮ Regular pairs in sparse random graphs I ⋮ Optimal packings of bounded degree trees ⋮ Partitioning problems in dense hypergraphs ⋮ On random sampling in uniform hypergraphs ⋮ Resolution of the Oberwolfach problem ⋮ On edge‐ordered Ramsey numbers ⋮ A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma ⋮ A fast new algorithm for weak graph regularity ⋮ The Induced Removal Lemma in Sparse Graphs ⋮ Estimating parameters associated with monotone properties ⋮ Short paths in \(\varepsilon \)-regular pairs and small diameter decompositions of dense graphs ⋮ Ramsey numbers for sparse graphs ⋮ Ramsey numbers of books and quasirandomness
