Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
From MaRDI portal
Publication:3520066
DOI10.1007/978-3-540-75225-7_24zbMath1142.68404OpenAlexW1532569127MaRDI QIDQ3520066
Publication date: 19 August 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-75225-7_24
Computational learning theory (68Q32) Graph theory (including graph drawing) in computer science (68R10)
Related Items (16)
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 ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ Reconstructing Markov processes from independent and anonymous experiments ⋮ Non-adaptive learning of a hidden hypergraph ⋮ Unnamed Item ⋮ Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions ⋮ Reconstruction and verification of chordal graphs with a distance oracle ⋮ Network construction with subgraph connectivity constraints ⋮ Optimal query complexity bounds for finding graphs ⋮ Network verification via routing table queries ⋮ Reconstructing Weighted Graphs with Minimal Query Complexity ⋮ Unnamed Item ⋮ Non-adaptive Learning of a Hidden Hypergraph ⋮ Topology discovery of sparse random graphs with few participants ⋮ On Parity Check (0,1)-Matrix over $\mathbb{Z}_p$
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the longest path algorithm for reconstructing trees from distance matrices
- An optimal algorithm to reconstruct trees from additive distance data
- Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
- Property testing and its connection to learning and approximation
- Learning a Hidden Matching
- Learning Theory
- Learning a Hidden Subgraph
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Optimal reconstruction of graphs under the additive model
This page was built for publication: Learning and Verifying Graphs Using Queries with a Focus on Edge Counting