Optimal query complexity bounds for finding graphs
From MaRDI portal
Recommendations
- Optimally reconstructing weighted graphs using queries
- Reconstructing weighted graphs with minimal query complexity
- Reconstructing weighted graphs with minimal query complexity
- Toward a deterministic polynomial time algorithm with optimal additive query complexity
- Toward a deterministic polynomial time algorithm with optimal additive query complexity
Cites work
- scientific article; zbMATH DE number 5957397 (Why is no real title available?)
- scientific article; zbMATH DE number 41347 (Why is no real title available?)
- scientific article; zbMATH DE number 3532378 (Why is no real title available?)
- scientific article; zbMATH DE number 1222833 (Why is no real title available?)
- scientific article; zbMATH DE number 194544 (Why is no real title available?)
- scientific article; zbMATH DE number 774007 (Why is no real title available?)
- scientific article; zbMATH DE number 5485589 (Why is no real title available?)
- scientific article; zbMATH DE number 3226595 (Why is no real title available?)
- scientific article; zbMATH DE number 3099315 (Why is no real title available?)
- A Combinatory Detection Problem
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- An Estimate for Concentration Functions
- Graph-Theoretic Concepts in Computer Science
- Learning Theory
- Learning a Hidden Matching
- Learning a Hidden Subgraph
- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
- On \(B_ 2\)-sequences of vectors
- On a lemma of Littlewood and Offord
- On the Fourier spectrum of monotone functions
- On the Increase of Dispersion of Sums of Independent Random Variables
- On the Kolmogorov-Rogozin inequality for the concentration function
- On the concentration function of a sum of independent random variables
- Optimal reconstruction of graphs under the additive model
- Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
- Reconstructing weighted graphs with minimal query complexity
Cited in
(21)- Optimal query complexity for reconstructing hypergraphs
- Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
- Toward a deterministic polynomial time algorithm with optimal additive query complexity
- A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries
- scientific article; zbMATH DE number 1099637 (Why is no real title available?)
- Exact learning from an honest teacher that answers membership queries
- scientific article; zbMATH DE number 7651142 (Why is no real title available?)
- Reconstructing weighted graphs with minimal query complexity
- Toward a deterministic polynomial time algorithm with optimal additive query complexity
- Exact learning of multitrees and almost-trees using path queries
- On triangle estimation using tripartite independent set queries
- Query efficient implementation of graphs of bounded clique-width
- Generalized framework for group testing: queries, feedbacks and adversaries
- Network verification via routing table queries
- scientific article; zbMATH DE number 1988012 (Why is no real title available?)
- Optimally reconstructing weighted graphs using queries
- Reconstructing weighted graphs with minimal query complexity
- scientific article; zbMATH DE number 4035882 (Why is no real title available?)
- Relative expressive power of navigational querying on graphs
- On the Complexity of Finding an Unknown Cut Via Vertex Queries
- Linear time construction of indexable elastic founder graphs
This page was built for publication: Optimal query complexity bounds for finding graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991004)
