Approximately Counting Embeddings into Random Graphs

DOI10.1007/978-3-540-85363-3_33MaRDI QIDQ5900477zbMATH OpenOpenAlexFDO

Authors Shiva Prasad Kasiviswanathan, Martin Fürer

Publication date 27 November 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85363-3_33

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Approximately counting embeddings into random graphs
• Counting subgraphs via homomorphisms
• Faster algorithms for counting subgraphs in sparse graphs
• Faster algorithms for finding and counting subgraphs
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs

Cited in

(6)

• Graph sampling with applications to estimating the number of pattern embeddings and the parameters of a statistical relational model
• Linking number and writhe in random linear embeddings of graphs
• Embedding large graphs into a random graph
• Counting subgraphs via homomorphisms
• Approximately counting embeddings into random graphs
• Estimating global subgraph counts by sampling

This page was built for publication: Approximately Counting Embeddings into Random Graphs

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