Approximately counting embeddings into random graphs

DOI10.1017/S0963548314000339MaRDI QIDQ5891884zbMATH OpenFDO

Authors Shiva Prasad Kasiviswanathan, Martin Fürer

Publication date 14 November 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548314000339

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

Cites work

• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• An analysis of Monte Carlo algorithm for estimating the permanent
• Approximately counting cliques
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• Approximating the Permanent
• Approximating the permanent: A simple approach
• Color-coding
• Counting the Number of Hamilton Cycles in Random Digraphs
• Embedding Graphs with Bounded Treewidth into Their Optimal Hypercubes
• Estimating the Efficiency of Backtrack Programs
• FSTTCS 2004: Foundations of software technology and theoretical computer science. 24th international conference, Chennai, India, December 16--18, 2004. Proceedings.
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• scientific article; zbMATH DE number 986986 (Why is no real title available?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Pattern associativity and the retrieval of semantic networks
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• Polynomial-Time Approximation Algorithms for the Ising Model
• Random generation of combinatorial structures from a uniform distribution
• Sampling binary contingency tables with a greedy start
• Spanning Subgraphs of Random Graphs
• The complexity of computing the permanent
• The Parameterized Complexity of Counting Problems

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 in Degenerate Graphs
• 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 Q5891884)