Reconstruction and verification of chordal graphs with a distance oracle

DOI10.1016/J.TCS.2021.01.006MaRDI QIDQ2227489zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

chordal graphdistance oracleinterval graphreconstructionverification

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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

Cites work

• An optimal algorithm to reconstruct trees from additive distance data
• Graph Classes: A Survey
• Graph reconstruction and verification
• Graph reconstruction with a betweenness oracle
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 41347 (Why is no real title available?)
• scientific article; zbMATH DE number 2079368 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Learning a Hidden Matching
• Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
• Network Discovery and Verification with Distance Queries
• On the longest path algorithm for reconstructing trees from distance matrices
• Optimal reconstruction of graphs under the additive model
• Optimally reconstructing weighted graphs using queries
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Reconstructing weighted graphs with minimal query complexity
• Representation of a finite graph by a set of intervals on the real line

Cited in

(7)

• A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries
• Near-linear query complexity for graph inference
• Graph reconstruction with a betweenness oracle
• Graph reconstruction and verification
• Graph reconstruction via distance oracles
• Exact learning of multitrees and almost-trees using path queries
• Quasi-linear distance query reconstruction for graphs of bounded treelength

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)