The complexity of the Approximate Multiple Pattern Matching Problem for random strings

DOI10.4230/LIPICS.AOFA.2020.24OpenAlexW3038001709MaRDI QIDQ5874424FDOQ5874424

Authors: Clément Requilé, Dimbinaina Ralaivaosaona, Stephan Wagner 

Publication date: 7 February 2023

Full work available at URL: https://hal.science/hal-03214615

Recommendations

• Subgraph statistics in subcritical graph classes
• Random graphs from a block-stable class
• Blocks in constrained random graphs with fixed average degree
• On the block number of graphs
• The Maximum Block Size of Critical Random Graphs
• Expected Maximum Block Size in Critical Random Graphs
• Modular statistics for subgraph counts in sparse random graphs
• On Subgraph Sizes in Random Graphs
• Local limit theorems for subgraph counts
• Distribution of subgraphs of random regular graphs

zbMATH Keywords

number of edgesnumber of blocksnumber of spanning treessubcritical graph classblock statistic

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Cited In (2)

• A proof of the block model threshold conjecture
• Expected Maximum Block Size in Critical Random Graphs

This page was built for publication: The complexity of the Approximate Multiple Pattern Matching Problem for random strings

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