Space-efficient biconnected components and recognition of outerplanar graphs
From MaRDI portal
Publication:666673
DOI10.1007/s00453-018-0464-zzbMath1444.68077OpenAlexW2807889815MaRDI QIDQ666673
Dieter Kratsch, Frank Kammer, Moritz Laudahn
Publication date: 11 March 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6468/
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (3)
Space-efficient vertex separators for treewidth ⋮ Unnamed Item ⋮ Simple 2^f-Color Choice Dictionaries
Cites Work
- Path-based depth-first search for strong and biconnected components
- Reprint of: Memory-constrained algorithms for simple polygons
- Selection and sorting with limited storage
- Linear algorithms to recognize outerplanar and maximal outerplanar graphs
- Characterizations of outerplanar graphs
- A simple test on 2-vertex- and 2-edge-connectivity
- Rank-select indices without tears
- Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
- Relationships between nondeterministic and deterministic tape complexities
- Improved Space Efficient Algorithms for BFS, DFS and Applications
- Depth-First Search Using $$O(n)$$ Bits
- Space-efficient Basic Graph Algorithms
- Space-Time Trade-offs for Stack-Based Algorithms
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- Undirected connectivity in log-space
- Graph Classes: A Survey
- Tight Lower Bounds for st-Connectivity on the NNJAG Model
- Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs
- Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits
- Space-Efficient Plane-Sweep Algorithms.
- Space-Efficient Euler Partition and Bipartite Edge Coloring
- Depth-First Search and Linear Graph Algorithms
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Space-efficient biconnected components and recognition of outerplanar graphs
