Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Elberfeld, Michael, Kammer, Frank, Meintrup, Johannes
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings
by: Hammer, Nina, et al.
Published: (2022)

Succinct Planar Encoding with Minor Operations
by: Kammer, Frank, et al.
Published: (2023)

Sorting and Ranking of Self-Delimiting Numbers with Applications to Outerplanar Graph Isomorphism
by: Kammer, Frank, et al.
Published: (2020)

Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
by: Dogeas, Konstantinos, et al.
Published: (2023)

Space-Efficient Graph Kernelizations
by: Kammer, Frank, et al.
Published: (2020)

Succinct Graph Representations and Algorithmic Applications
by: Ullah, Ahammed, et al.
Published: (2026)

Succinct Encodings of Binary Trees with Application to AVL Trees
by: Chizewer, Jeremy, et al.
Published: (2023)

Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
by: Balakrishnan, Girish, et al.
Published: (2023)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
by: Balakrishnan, Girish, et al.
Published: (2024)

Testing Depth First Search Numbering
by: Czumaj, Artur, et al.
Published: (2025)

Succinct Data Structures for Segments
by: Bille, Philip, et al.
Published: (2024)

Revisiting a Successful Reduction Rule for Dominating Set
by: Geis, Lukas, et al.
Published: (2025)

Succinct Preferential Attachment Graphs
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
by: Kenneth, Yotam, et al.
Published: (2023)

SPIDER: Improved Succinct Rank and Select Performance
by: Laws, Matthew D., et al.
Published: (2024)

Fast and Efficient Parallel Breadth-First Search with Power-law Graph Transformation
by: Jiang, Zite, et al.
Published: (2020)

Succinct Data Structures for Baxter Permutation and Related Families
by: Chakraborty, Sankardeep, et al.
Published: (2024)

Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations
by: Ferragina, Paolo, et al.
Published: (2025)

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
by: Kuszmaul, William, et al.
Published: (2025)

Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs
by: Alaoui, Ziad Ismaili, et al.
Published: (2026)

Efficient Semi-External Breadth-First Search
by: Wan, Xiaolong, et al.
Published: (2025)

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing
by: Lehmann, Hans-Peter, et al.
Published: (2025)

Small Space Encoding and Recognition of $k$-Palindromic Prefixes
by: Bathie, Gabriel, et al.
Published: (2024)

Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion
by: McCauley, Samuel
Published: (2024)

Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space
by: Jang, Jihoon, et al.
Published: (2025)

Dynamic Breadth First Search with Predictions
by: Khan, Shahbaz, et al.
Published: (2026)

CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions
by: Coleman, Benjamin, et al.
Published: (2023)

Preprocessing to Reduce the Search Space for Odd Cycle Transversal
by: Jansen, Bart M. P., et al.
Published: (2024)

Theoretical Analysis of Byte-Pair Encoding
by: Kozma, László, et al.
Published: (2024)

Graph-Based Algorithms for Diverse Similarity Search
by: Anand, Piyush, et al.
Published: (2025)

AutoCSF: Provably Space-Efficient Indexing of Skewed Key-Value Workloads via Filter-Augmented Compressed Static Functions
by: Ramos, David Torres, et al.
Published: (2026)

Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking
by: Dolev, Shlomi
Published: (2025)

Counting Patterns in Degenerate Graphs in Constant Space
by: Komarath, Balagopal, et al.
Published: (2025)

CuckooGraph: A Scalable and Space-Time Efficient Data Structure for Large-Scale Dynamic Graphs
by: Fan, Zhuochen, et al.
Published: (2024)

Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set
by: Donkers, Huib, et al.
Published: (2021)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search
by: Li, Binhong, et al.
Published: (2025)

Scalable Similarity Search over Large Attributed Bipartite Graphs
by: Ou, Xi, et al.
Published: (2025)

Skyline-First Traversal as a Control Mechanism for Multi-Criteria Graph Search
by: Tacheny, Nicolas
Published: (2026)