Graph Reconstruction via MIS Queries

Christian Konrad, Conor O’Sullivan, Victor Traistaru

Type: Preprint

Publication Date: 2024-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2401.05845

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Lower bounds for graph reconstruction with maximal independent set queries	2024	Lukas Michel Alex Scott
+	Graph Reconstruction via Distance Oracles	2013	Claire Mathieu Hang Zhou
+	Graph Connectivity and Single Element Recovery via Linear and OR Queries	2020	Sepehr Assadi Deeparnab Chakrabarty Sanjeev Khanna
+ PDF Chat	Graph Reconstruction from Noisy Random Subgraphs	2024	Andrew McGregor Rik Sengupta
+	Finding a Hidden Edge	2022	Ron Kupfer Noam Nisan
+	Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries	2022	Raghavendra Addanki Andrew McGregor Cameron Musco
+	Optimal distance query reconstruction for graphs without long induced cycles	2023	Paul Bastide Carla Groenland
+	Near-Optimal Deterministic Vertex-Failure Connectivity Oracles	2022	Yaowei Long Thatchaphol Saranurak
+	A tight bound for the clique query problem in two rounds	2021	Uriel Feige Tom Ferster
+	A Simple Algorithm for Graph Reconstruction	2021	Claire Mathieu Hang Zhou
+ PDF Chat	Reconstructing random graphs from distance queries	2024	Michael Krivelevich Maksim Zhukovskii
+	Finding cliques and dense subgraphs using edge queries	2023	Endre Csóka András Pongrácz
+	Nearly optimal edge estimation with independent set queries	2019	Xi Chen Amit Levi Erik Waingarten
+ PDF Chat	Near-Optimal Deterministic Vertex-Failure Connectivity Oracles	2022	Yaowei Long Thatchaphol Saranurak
+	Near-Linear Query Complexity for Graph Inference	2014	Sampath Kannan Claire Mathieu Hang Zhou
+	Graph Reconstruction in the Congested Clique	2017	Pedro Montealegre Sebastian Perez-Salazar Iván Rapaport Ioan Todinca
+	Graph Reconstruction in the Congested Clique	2017	Pedro Montealegre Sebastian Perez-Salazar Iván Rapaport Ioan Todinca
+	A Framework for Searching in Graphs in the Presence of Errors	2018	Dariusz Dereniowski Stefan Tiegel Przemysław Uznański Daniel Wolleb-Graf
+ PDF Chat	On Approximating the Number of $k$-Cliques in Sublinear Time	2020	Talya Eden Dana Ron C. Seshadhri
+	On Learning Graphs with Edge-Detecting Queries	2018	Hasan Abasi Nader H. Bshouty

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors