Reconstruction and verification of chordal graphs with a distance oracle

DOI10.1016/J.TCS.2021.01.006zbMATH Open1497.68395OpenAlexW3118852340MaRDI QIDQ2227489FDOQ2227489

Jianxin Wang, Yongjie Yang, Wen-Jun Li, Guozhen Rong

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

verificationreconstructioninterval graphchordal graphdistance oracle

Mathematics Subject Classification ID

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Classes: A Survey
• Representation of a finite graph by a set of intervals on the real line
• 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
• 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 (3)

• A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries
• Title not available (Why is that?)
• Exact learning of multitrees and almost-trees using path queries

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Distance Approximating Trees for Chordal and Dually Chordal Graphs 👍 👎
• Graph-Theoretic Concepts in Computer Science 👍 👎
• An efficient representation of chordal graphs 👍 👎
• Graph Reconstruction via Distance Oracles 👍 👎
• Graph reconstruction with a betweenness oracle 👍 👎
• Distance Oracles for Vertex-Labeled Graphs 👍 👎
• Approximate Distance Oracle in O(n2) Time and O(n) Space for Chordal Graphs 👍 👎

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)