Graph reconstruction via MIS queries
From MaRDI portal
Cites work
- A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries
- A simple algorithm for graph reconstruction
- An Improved Distributed Algorithm for Maximal Independent Set
- Approximating Average Parameters of Graphs
- Constructing large matchings via query access to a maximal matching oracle
- Edge estimation with independent set oracles
- Graph reconstruction and verification
- Graph reconstruction from random subgraphs
- Graph reconstruction with a betweenness oracle
- Improved massively parallel computation algorithms for MIS, matching, and vertex cover
- Learning a hidden graph using \(O(\log n)\)queries per edge
- Learning a Hidden Matching
- Learning a Hidden Subgraph
- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
- Maximum matching via maximal matching queries
- Non-adaptive edge counting and sampling via bipartite independent set queries
- On learning graphs with edge-detecting queries
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Reconstruction and verification of chordal graphs with a distance oracle
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
This page was built for publication: Graph reconstruction via MIS queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296712)
