Learning a Hidden Subgraph
From MaRDI portal
Publication:5317581
DOI10.1137/S0895480103431071zbMath1078.68111MaRDI QIDQ5317581
Publication date: 16 September 2005
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Lower bounds for cover-free families ⋮ A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Learning Boolean halfspaces with small weights from membership queries ⋮ Constraining the number of positive responses in adaptive, non-adaptive, and two-stage group testing ⋮ On graphs that contain exactly \(k\) copies of a subgraph, and a related problem in search theory ⋮ Bounds and algorithms for generalized superimposed codes ⋮ Reconstructing Markov processes from independent and anonymous experiments ⋮ Non-adaptive learning of a hidden hypergraph ⋮ Learning and Verifying Graphs Using Queries with a Focus on Edge Counting ⋮ Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions ⋮ Learning a hidden graph ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Learning a hidden uniform hypergraph ⋮ Group Testing with Multiple Mutually-Obscuring Positives ⋮ Network construction with subgraph connectivity constraints ⋮ Reconstruction of hidden graphs and threshold group testing ⋮ Optimal query complexity bounds for finding graphs ⋮ A new kind of selectors and their applications to conflict resolution in wireless multichannels networks ⋮ COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY ⋮ Low-weight superimposed codes and related combinatorial structures: bounds and applications ⋮ Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries ⋮ Nonadaptive algorithms for threshold group testing ⋮ Reconstructing Weighted Graphs with Minimal Query Complexity ⋮ Unnamed Item ⋮ Non-adaptive Learning of a Hidden Hypergraph
