Optimal In-place Algorithms for Basic Graph Problems

DOI10.1007/978-3-030-48966-3_10MaRDI QIDQ5041185zbMATH OpenOpenAlexFDO

Authors Sankardeep Chakraborty, Kunihiko Sadakane, Srinivasa Rao Satti

Publication date 13 October 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Recommendations

• Linear-time in-place DFS and BFS on the word RAM
• A framework for in-place graph algorithms
• Space-efficient basic graph algorithms
• Frameworks for designing in-place graph algorithms
• Improved space efficient algorithms for BFS, DFS and applications

Cites work

• A framework for in-place graph algorithms
• A note on finding the bridges of a graph
• A simple test on 2-vertex- and 2-edge-connectivity
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• An implicit data structure supporting insertion, deletion, and search in O( ^ 2\,n) time
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Catalytic computation
• Computing an st-numbering
• Computing with a full memory: catalytic space
• Constant-work-space algorithms for geometric problems
• Depth-First Search and Linear Graph Algorithms
• Depth-First Search Using O(n) Bits
• Efficient Storage and Retrieval by Content and Address of Static Files
• Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
• Graph theory
• scientific article; zbMATH DE number 4062610 (Why is no real title available?)
• scientific article; zbMATH DE number 2038723 (Why is no real title available?)
• Implicit dictionaries with O(1) modifications per update and fast search
• In-Place Suffix Sorting
• Indexing graph search trees and applications
• Introduction to algorithms.
• Linear-time in-place DFS and BFS on the word RAM
• Multi-pass geometric algorithms
• On graph problems in a semi-streaming model
• Optimal time-space tradeoff for the 2D convex-hull problem
• Radix Sorting with No Extra Space
• Reprint of: Memory-constrained algorithms for simple polygons
• Selection and sorting in the ``restore model
• Selection and sorting with limited storage
• Selection from read-only memory with limited workspace
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Space efficient algorithms for breadth-depth search
• Space efficient linear time algorithms for BFS, DFS and applications
• Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
• Space-efficient basic graph algorithms
• Space-time trade-offs for stack-based algorithms
• The space complexity of approximating the frequency moments
• Towards in-place geometric algorithms and data structures
• Upper bounds for time-space trade-offs in sorting and selection

Cited in

(4)

• Frameworks for designing in-place graph algorithms
• Linear-time in-place DFS and BFS on the word RAM
• Space-efficient graph kernelizations
• Co-lexicographically ordering automata and regular languages. I

This page was built for publication: Optimal In-place Algorithms for Basic Graph Problems

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