Image de couverture de livre

Graph Reconstruction with a Connected Components Oracle

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Harviainen, Juha, Parviainen, Pekka
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Quantum Speedups for Bayesian Network Structure Learning
par: Harviainen, Juha, et autres
Publié: (2023)

Exact and Approximate Algorithms for Polytree Learning
par: Harviainen, Juha, et autres
Publié: (2026)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
par: Kosinas, Evangelos
Publié: (2025)

Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework
par: Sena, Francisco, et autres
Publié: (2026)

The Power of Graph Doubling: Computing Ultrabubbles in a Bidirected Graph by Reducing to Weak Superbubbles
par: Schmidt, Sebastian, et autres
Publié: (2026)

Space Complexity of Vertex Connectivity Oracles
par: Pettie, Seth, et autres
Publié: (2022)

Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity
par: Long, Yaowei, et autres
Publié: (2024)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
par: Li, Xizhe, et autres
Publié: (2026)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
par: Neiman, Ofer, et autres
Publié: (2026)

Connectivity Oracles for Predictable Vertex Failures
par: Hu, Bingbing, et autres
Publié: (2023)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
par: Ahi, Mridul, et autres
Publié: (2025)

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
par: Manoharan, Vignesh, et autres
Publié: (2025)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
par: Black, Hadley, et autres
Publié: (2025)

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
par: Kumar, Akash, et autres
Publié: (2026)

Reconfiguring Multiple Connected Components with Size Multiset Constraints
par: Nakahata, Yu
Publié: (2025)

Linear Kernels for $l$-Exact Component Order Connectivity
par: Liu, Yuxi, et autres
Publié: (2026)

Fully Dynamic Strongly Connected Components in Planar Digraphs
par: Karczmarz, Adam, et autres
Publié: (2024)

Hamming Distance Oracle
par: Boneh, Itai, et autres
Publié: (2024)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
par: Georgiadis, Loukas, et autres
Publié: (2026)

Hyper-distance Oracles in Hypergraphs
par: Preti, Giulia, et autres
Publié: (2023)

Distributed Distance Sensitivity Oracles
par: Manoharan, Vignesh, et autres
Publié: (2024)

Temporal Graph Reconfiguration for Always-Connected Graphs
par: Sievers, Paul, et autres
Publié: (2025)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
par: Kumar, Mithilesh, et autres
Publié: (2016)

Identifying all snarls and superbubbles in linear-time, via a unified SPQR-tree framework
par: Sena, Francisco, et autres
Publié: (2025)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
par: Chang, Hsien-Chih, et autres
Publié: (2025)

Combinatorial Optimization using Comparison Oracles
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Fault-Tolerant ST-Diameter Oracles
par: Bilò, Davide, et autres
Publié: (2023)

Optimal Sensitivity Oracle for Steiner Mincut
par: Bhanja, Koustav
Publié: (2024)

Connectivity Labeling in Faulty Colored Graphs
par: Petruschka, Asaf, et autres
Publié: (2024)

Exploration of Always $S$-Connected Temporal Graphs
par: Adamson, Duncan, et autres
Publié: (2026)

Improved Algorithms for Clustering with Noisy Distance Oracles
par: Pradhan, Pinki, et autres
Publié: (2026)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
par: Bilò, Davide, et autres
Publié: (2024)

Path-Reporting Distance Oracles with Linear Size
par: Neiman, Ofer, et autres
Publié: (2024)

Approximate Distance Sensitivity Oracles in Subquadratic Space
par: Bilò, Davide, et autres
Publié: (2023)

Sublinear Spectral Clustering Oracle with Little Memory
par: Shen, Ranran, et autres
Publié: (2026)

Nearly Optimal Fault Tolerant Distance Oracle
par: Dey, Dipan, et autres
Publié: (2024)

Fault-Tolerant Approximate Distance Oracles with a Source Set
par: Dey, Dipan, et autres
Publié: (2025)

Connectivity-Preserving Minimum Separator in AT-free Graphs
par: Kenig, Batya
Publié: (2025)

Graph Traversal via Connected Mobile Agents
par: Jana, Saswata, et autres
Publié: (2025)

Approximation Schemes for Planar Graph Connectivity Problems
par: Neuwohner, Meike, et autres
Publié: (2025)