Space-efficient biconnected components and recognition of outerplanar graphs

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/

zbMATH Keywords

graph algorithmscut verticesspace efficiencybiconnected components(maximal) outerplanar graphs

Mathematics Subject Classification ID

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