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

DOI10.4230/LIPICS.AOFA.2020.24MaRDI QIDQ5874424zbMATH OpenOpenAlexFDO

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

Publication date 7 February 2023

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

zbMATH Keywords

number of edgesnumber of blocksnumber of spanning treessubcritical graph classblock statistic

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

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

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)