A divide-and-conquer approach for reconstruction of \C_ 5\-free graphs via betweenness queries

DOI10.1016/J.TCS.2022.03.008MaRDI QIDQ2143136zbMATH OpenOpenAlexFDO

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

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

chordal graphsdistance-hereditary graphsgraph reconstruction\(\{ C_{\geq 5} \}\)-free graphsbetweenness oracle

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Graph reconstruction with a betweenness oracle
• Graph reconstruction via distance oracles
• Near-linear query complexity for graph inference
• Optimal reconstruction of graphs under the additive model

Cites work

• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A polynomial kernel for distance-hereditary vertex deletion
• Distance-hereditary graphs
• Graph reconstruction and verification
• Graph reconstruction with a betweenness oracle
• Graph verification with a betweenness oracle
• Learning a Hidden Subgraph
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
• Optimal query complexity bounds for finding graphs
• Proof of a recursive program: Quicksort
• Quicksort with Equal Keys
• Reconstructing cactus graphs from shortest path information (extended abstract)
• Reconstruction and verification of chordal graphs with a distance oracle
• The analysis of Quicksort programs

Cited in

(1)

• Exact learning of multitrees and almost-trees using path queries

Describes a project that uses

Uses Software

• Quicksort

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2143136)