Imagen de Portada

Graph Reconstruction with a Connected Components Oracle

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Harviainen, Juha, Parviainen, Pekka
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Quantum Speedups for Bayesian Network Structure Learning
por: Harviainen, Juha, et al.
Publicado: (2023)

Exact and Approximate Algorithms for Polytree Learning
por: Harviainen, Juha, et al.
Publicado: (2026)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
por: Kosinas, Evangelos
Publicado: (2025)

Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework
por: Sena, Francisco, et al.
Publicado: (2026)

The Power of Graph Doubling: Computing Ultrabubbles in a Bidirected Graph by Reducing to Weak Superbubbles
por: Schmidt, Sebastian, et al.
Publicado: (2026)

Space Complexity of Vertex Connectivity Oracles
por: Pettie, Seth, et al.
Publicado: (2022)

Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity
por: Long, Yaowei, et al.
Publicado: (2024)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
por: Li, Xizhe, et al.
Publicado: (2026)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
por: Neiman, Ofer, et al.
Publicado: (2026)

Connectivity Oracles for Predictable Vertex Failures
por: Hu, Bingbing, et al.
Publicado: (2023)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
por: Ahi, Mridul, et al.
Publicado: (2025)

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
por: Manoharan, Vignesh, et al.
Publicado: (2025)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
por: Black, Hadley, et al.
Publicado: (2025)

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
por: Kumar, Akash, et al.
Publicado: (2026)

Reconfiguring Multiple Connected Components with Size Multiset Constraints
por: Nakahata, Yu
Publicado: (2025)

Linear Kernels for $l$-Exact Component Order Connectivity
por: Liu, Yuxi, et al.
Publicado: (2026)

Fully Dynamic Strongly Connected Components in Planar Digraphs
por: Karczmarz, Adam, et al.
Publicado: (2024)

Hamming Distance Oracle
por: Boneh, Itai, et al.
Publicado: (2024)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
por: Georgiadis, Loukas, et al.
Publicado: (2026)

Hyper-distance Oracles in Hypergraphs
por: Preti, Giulia, et al.
Publicado: (2023)

Distributed Distance Sensitivity Oracles
por: Manoharan, Vignesh, et al.
Publicado: (2024)

Temporal Graph Reconfiguration for Always-Connected Graphs
por: Sievers, Paul, et al.
Publicado: (2025)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
por: Kumar, Mithilesh, et al.
Publicado: (2016)

Identifying all snarls and superbubbles in linear-time, via a unified SPQR-tree framework
por: Sena, Francisco, et al.
Publicado: (2025)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
por: Chang, Hsien-Chih, et al.
Publicado: (2025)

Combinatorial Optimization using Comparison Oracles
por: Cohen-Addad, Vincent, et al.
Publicado: (2025)

Fault-Tolerant ST-Diameter Oracles
por: Bilò, Davide, et al.
Publicado: (2023)

Optimal Sensitivity Oracle for Steiner Mincut
por: Bhanja, Koustav
Publicado: (2024)

Connectivity Labeling in Faulty Colored Graphs
por: Petruschka, Asaf, et al.
Publicado: (2024)

Exploration of Always $S$-Connected Temporal Graphs
por: Adamson, Duncan, et al.
Publicado: (2026)

Improved Algorithms for Clustering with Noisy Distance Oracles
por: Pradhan, Pinki, et al.
Publicado: (2026)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
por: Bilò, Davide, et al.
Publicado: (2024)

Path-Reporting Distance Oracles with Linear Size
por: Neiman, Ofer, et al.
Publicado: (2024)

Approximate Distance Sensitivity Oracles in Subquadratic Space
por: Bilò, Davide, et al.
Publicado: (2023)

Sublinear Spectral Clustering Oracle with Little Memory
por: Shen, Ranran, et al.
Publicado: (2026)

Nearly Optimal Fault Tolerant Distance Oracle
por: Dey, Dipan, et al.
Publicado: (2024)

Fault-Tolerant Approximate Distance Oracles with a Source Set
por: Dey, Dipan, et al.
Publicado: (2025)

Connectivity-Preserving Minimum Separator in AT-free Graphs
por: Kenig, Batya
Publicado: (2025)

Graph Traversal via Connected Mobile Agents
por: Jana, Saswata, et al.
Publicado: (2025)

Approximation Schemes for Planar Graph Connectivity Problems
por: Neuwohner, Meike, et al.
Publicado: (2025)