Graph reconstruction with a betweenness oracle

DOI10.4230/LIPICS.STACS.2016.5MaRDI QIDQ4601854zbMATH OpenOpenAlexFDO

Authors Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, Morten Stöckel

Publication date 24 January 2018

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/5706/pdf/6.pdf/

zbMATH Keywords

bounded-degree graphsgraph reconstructionquery complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Graph reconstruction via distance oracles
• Graph verification with a betweenness oracle
• Graph reconstruction and verification
• Near-linear query complexity for graph inference
• Reconstruction and verification of chordal graphs with a distance oracle

Cited in

(10)

• Reconstituting beta graphs into an efficacious system
• A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries
• Reconstruction and verification of chordal graphs with a distance oracle
• Reconstructing cactus graphs from shortest path information (extended abstract)
• Near-linear query complexity for graph inference
• Graph reconstruction and verification
• Graph verification with a betweenness oracle
• Graph reconstruction via distance oracles
• Exact learning of multitrees and almost-trees using path queries
• Learning hypertrees from shortest path queries

This page was built for publication: Graph reconstruction with a betweenness oracle

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