A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries

DOI10.1016/j.tcs.2022.03.008OpenAlexW4220724300MaRDI QIDQ2143136

Guozhen Rong, Yongjie Yang, Jianxin Wang, Wenjun Li

Publication date: 31 May 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.03.008

zbMATH Keywords

distance-hereditary graphschordal graphsgraph reconstruction\(\{ C_{\geq 5} \}\)-free graphsbetweenness oracle

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Exact learning of multitrees and almost-trees using path queries

Uses Software

• Quicksort

Cites Work

• Unnamed Item
• Unnamed Item
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Optimal query complexity bounds for finding graphs
• Distance-hereditary graphs
• The analysis of Quicksort programs
• Reconstruction and verification of chordal graphs with a distance oracle
• Reconstructing Cactus Graphs from Shortest Path Information
• Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
• Quicksort with Equal Keys
• Graph reconstruction with a betweenness oracle
• Graph Reconstruction and Verification
• Learning a Hidden Subgraph
• Proof of a recursive program: Quicksort
• A polynomial kernel for distance-hereditary vertex deletion

This page was built for publication: A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries