Fast breadth-first search in still less space

DOI10.1007/978-3-030-30786-8_8MaRDI QIDQ2301537zbMATH OpenOpenAlexFDO

Authors Torben Hagerup

Publication date 24 February 2020

Full work available at URL https://arxiv.org/abs/1812.10950

zbMATH Keywords

BFSchoice dictionariesgraph algorithmsin-place chain techniquespace efficiencysuccinct data structures

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Space efficient algorithms for breadth-depth search
• scientific article; zbMATH DE number 5734730
• Theory and techniques for synthesizing efficient breadth-first search algorithms
• scientific article; zbMATH DE number 1947435
• Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
• On dynamic breadth-first search in external-memory
• Space efficient linear time algorithms for BFS, DFS and applications
• Improved space efficient algorithms for BFS, DFS and applications
• Extended breadth-first search algorithm in practice

Cited in

(7)

• In-place initializable arrays
• Space efficient algorithms for breadth-depth search
• Linear-time in-place DFS and BFS on the word RAM
• Breadth-first numbering
• scientific article; zbMATH DE number 5734730 (Why is no real title available?)
• A constant-time colored choice dictionary with almost robust iteration
• Succinct data structure for path graphs

This page was built for publication: Fast breadth-first search in still less space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2301537)