Reconstruction and verification of chordal graphs with a distance oracle
DOI10.1016/J.TCS.2021.01.006zbMATH Open1497.68395OpenAlexW3118852340MaRDI QIDQ2227489FDOQ2227489
Authors: Guozhen Rong, Wen-Jun Li, Yongjie Yang, Jianxin Wang 
Publication date: 15 February 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.01.006
Recommendations
- Graph reconstruction via distance oracles
- Graph reconstruction with a betweenness oracle
- Graph verification with a betweenness oracle
- Approximate distance oracle in \(O(n ^{2})\) time and \(O(n)\) space for chordal graphs
- Distance oracles for vertex-labeled graphs
- Chordal probe graphs (extended abstract)
- Exact distance oracles for planar graphs
- Graph reconstruction conjecture: reductions using complement, connectivity and distance
- Distance Approximating Trees for Chordal and Dually Chordal Graphs
- An efficient representation of chordal graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Graph Classes: A Survey
- Title not available (Why is that?)
- Representation of a finite graph by a set of intervals on the real line
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
- Learning a Hidden Matching
- Optimal reconstruction of graphs under the additive model
- Reconstructing weighted graphs with minimal query complexity
- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
- Optimally reconstructing weighted graphs using queries
- Graph-Theoretic Concepts in Computer Science
- Graph reconstruction and verification
- An optimal algorithm to reconstruct trees from additive distance data
- On the longest path algorithm for reconstructing trees from distance matrices
- Graph reconstruction with a betweenness oracle
- Network Discovery and Verification with Distance Queries
Cited In (7)
- Graph reconstruction with a betweenness oracle
- Graph reconstruction and verification
- A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries
- Graph reconstruction via distance oracles
- Title not available (Why is that?)
- Exact learning of multitrees and almost-trees using path queries
- Near-linear query complexity for graph inference
This page was built for publication: Reconstruction and verification of chordal graphs with a distance oracle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227489)
