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

DOI10.1016/J.TCS.2022.03.008OpenAlexW4220724300MaRDI QIDQ2143136FDOQ2143136

Guozhen Rong, Yongjie Yang, Jianxin Wang, Wen-Jun 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

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (1)

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

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)