Conjunctive queries on probabilistic graphs: the limits of approximability
From MaRDI portal
Cites work
- #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
- A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
- Combined tractability of query evaluation via tree automata and cycluits
- Computational transition at the uniqueness threshold
- Connecting knowledge compilation classes and width parameters
- Decomposable negation normal form
- Exact model counting of query expressions. Limitations of propositional methods
- FPTAS for counting monotone CNF
- High-confidence estimation of small s-t reliabilities in directed acyclic networks
- scientific article; zbMATH DE number 1946853 (Why is no real title available?)
- Incomplete Information in Relational Databases
- Knowledge compilation meets database theory: compiling queries to decision diagrams
- On the Lambert \(w\) function
- On tree width, bramble size, and expansion
- Probabilistic databases
- Provenance circuits for trees and treelike instances
- Provenance in databases: principles and applications
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The Complexity of Enumeration and Reliability Problems
- The dag-width of directed graphs
- The dichotomy of evaluating homomorphism-closed queries on probabilistic graphs
- The dichotomy of probabilistic inference for unions of conjunctive queries
- Uniform reliability for unbounded homomorphism-closed graph queries
- Uniform Reliability of Self-Join-Free Conjunctive Queries
- When is approximate counting for conjunctive queries tractable?
This page was built for publication: Conjunctive queries on probabilistic graphs: the limits of approximability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6902073)
