Optimal query complexity bounds for finding graphs
DOI10.1016/J.ARTINT.2010.02.003zbMATH Open1206.68228OpenAlexW2048252940MaRDI QIDQ991004FDOQ991004
Authors: Sung-Soon Choi, Jeong Han Kim 
Publication date: 2 September 2010
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2010.02.003
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
Fourier coefficientpseudo-Boolean functioncombinatorial searchcombinatorial group testinggraph findingcoin weighingLittlewood-Offord theorem
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- On the concentration function of a sum of independent random variables
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- On the Kolmogorov-Rogozin inequality for the concentration function
- Title not available (Why is that?)
- Title not available (Why is that?)
- An Estimate for Concentration Functions
- On a lemma of Littlewood and Offord
- Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
- Title not available (Why is that?)
- Learning a Hidden Matching
- Title not available (Why is that?)
- Learning a Hidden Subgraph
- Title not available (Why is that?)
- On the Fourier spectrum of monotone functions
- A Combinatory Detection Problem
- Graph-Theoretic Concepts in Computer Science
- Optimal reconstruction of graphs under the additive model
- On \(B_ 2\)-sequences of vectors
- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
- Learning Theory
- Title not available (Why is that?)
- Reconstructing weighted graphs with minimal query complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Increase of Dispersion of Sums of Independent Random Variables
Cited In (18)
- Reconstructing weighted graphs with minimal query complexity
- On triangle estimation using tripartite independent set queries
- Title not available (Why is that?)
- Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
- Reconstructing weighted graphs with minimal query complexity
- Generalized framework for group testing: queries, feedbacks and adversaries
- A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries
- Title not available (Why is that?)
- Exact learning from an honest teacher that answers membership queries
- Network verification via routing table queries
- Linear time construction of indexable elastic founder graphs
- Toward a deterministic polynomial time algorithm with optimal additive query complexity
- Title not available (Why is that?)
- Query efficient implementation of graphs of bounded clique-width
- Title not available (Why is that?)
- Exact learning of multitrees and almost-trees using path queries
- On the Complexity of Finding an Unknown Cut Via Vertex Queries
- Relative expressive power of navigational querying on 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)
