Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
From MaRDI portal
Recommendations
Cites work
- An optimal algorithm to reconstruct trees from additive distance data
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- scientific article; zbMATH DE number 5957397 (Why is no real title available?)
- scientific article; zbMATH DE number 3886512 (Why is no real title available?)
- scientific article; zbMATH DE number 3573787 (Why is no real title available?)
- scientific article; zbMATH DE number 2079368 (Why is no real title available?)
- Learning a Hidden Matching
- Learning a Hidden Subgraph
- Learning Theory
- On the longest path algorithm for reconstructing trees from distance matrices
- Optimal reconstruction of graphs under the additive model
- Property testing and its connection to learning and approximation
- Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
Cited in
(25)- Non-adaptive learning of a hidden hypergraph
- A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries
- Reconstruction and verification of chordal graphs with a distance oracle
- Network construction with subgraph connectivity constraints
- Exact learning from an honest teacher that answers membership queries
- Non-adaptive learning of a hidden hypergraph
- Topology discovery of sparse random graphs with few participants
- Linear Time Constructions of Some d-Restriction Problems
- Reconstructing weighted graphs with minimal query complexity
- Graph verification with a betweenness oracle
- Edge estimation with independent set oracles
- Network construction with ordered constraints
- On Parity Check (0,1)-Matrix over $\mathbb{Z}_p$
- Edge Estimation with Independent Set Oracles
- Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
- Learning spanning forests optimally in weighted undirected graphs with CUT queries
- Learning hypertrees from shortest path queries
- A query algorithm for learning a spanning forest in weighted undirected graphs
- Quasi-linear distance query reconstruction for graphs of bounded treelength
- Learning partitions using rank queries
- Finding the diameter of a tree with distance queries
- Reconstructing random graphs from distance queries
- Network verification via routing table queries
- Reconstructing Markov processes from independent and anonymous experiments
- Optimal query complexity bounds for finding graphs
This page was built for publication: Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3520066)
