Cover Image

Graph Reconstruction via MIS Queries

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Konrad, Christian, O'Sullivan, Conor, Traistaru, Victor
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Constructing Long Paths in Graph Streams
by: Konrad, Christian, et al.
Published: (2025)

Singing a MIS
by: Irani, Sandy, et al.
Published: (2025)

Efficient Trace Frequency Queries in Sparse Graphs
by: Awofeso, Christine, et al.
Published: (2025)

BD-Index: Scalable Biharmonic Distance Queries on Large Graphs via Divide-and-Conquer Indexing
by: Pan, Yueyang, et al.
Published: (2025)

Approximating Queries on Probabilistic Graphs
by: Amarilli, Antoine, et al.
Published: (2023)

Interval Selection in Sliding Windows
by: Alexandru, Cezar-Mihail, et al.
Published: (2024)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
by: Dalirrooyfard, Mina, et al.
Published: (2026)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
by: Khanna, Sanjeev, et al.
Published: (2026)

Streaming Maximal Matching with Bounded Deletions
by: Khanna, Sanjeev, et al.
Published: (2025)

Graph Reconstruction with a Connected Components Oracle
by: Harviainen, Juha, et al.
Published: (2025)

Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
by: Beretta, Lorenzo, et al.
Published: (2025)

Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
by: Zhao, Zhuowei, et al.
Published: (2025)

Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing
by: Eppstein, David, et al.
Published: (2025)

Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
by: Kaudan, Chirag, et al.
Published: (2026)

GORAM: Graph-oriented ORAM for Efficient Ego-centric Queries on Federated Graphs
by: Fan, Xiaoyu, et al.
Published: (2024)

When is String Reconstruction using de Bruijn Graphs Hard?
by: Bals, Ben, et al.
Published: (2025)

Sparse Graph Reconstruction and Seriation for Large-Scale Image Stacks
by: Yang, Fuming, et al.
Published: (2025)

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
by: Kamath, Gautam, et al.
Published: (2025)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
by: Bishnu, Arijit, et al.
Published: (2025)

Semi-Robust Communication Complexity of Maximum Matching
by: Huete, Gabriel Cipriani, et al.
Published: (2025)

Distance Reconstruction of Sparse Random Graphs
by: Bastide, Paul
Published: (2024)

Submodular Maximization in Exactly $n$ Queries
by: Balkanski, Eric, et al.
Published: (2024)

First Passage Percolation with Queried Hints
by: Karntikoon, Kritkorn, et al.
Published: (2024)

Learning Partitions using Rank Queries
by: Chakrabarty, Deeparnab, et al.
Published: (2024)

Parameterized Quantum Query Algorithms for Graph Problems
by: Terao, Tatsuya, et al.
Published: (2024)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Cut-Query Algorithms with Few Rounds
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

Query Complexity of the Metric Steiner Tree Problem
by: Chen, Yu, et al.
Published: (2022)

Sorted Range Reporting and Range Minima Queries
by: Akram, Waseem, et al.
Published: (2021)

Faster Iterative $ϕ$ Queries on the Positional BWT
by: Bonizzoni, Paola, et al.
Published: (2026)

Personalized PageRank Estimation in Undirected Graphs
by: Bertram, Christian, et al.
Published: (2026)

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)

Exact Learning of Weighted Graphs Using Composite Queries
by: Goodrich, Michael T., et al.
Published: (2025)

LLM Query Scheduling with Prefix Reuse and Latency Constraints
by: Dexter, Gregory, et al.
Published: (2025)

New Oracles and Labeling Schemes for Vertex Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Simpler O(1) Query Algorithm for Level Ancestors
by: Saxena, Sanjeev
Published: (2022)

Encodings for Range Minimum Queries over Bounded Alphabets
by: Jo, Seungbum, et al.
Published: (2026)

Scalable Multilevel and Memetic Signed Graph Clustering
by: Hausberger, Felix, et al.
Published: (2022)