Path-based depth-first search for strong and biconnected components
From MaRDI portal
Publication:294748
DOI10.1016/S0020-0190(00)00051-XzbMATH Open1339.68301WikidataQ56673385 ScholiaQ56673385MaRDI QIDQ294748FDOQ294748
Authors: Harold N. Gabow 
Publication date: 16 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S002001900000051X?np=y
Recommendations
- On finding the strongly connected components in a directed graph
- A space-efficient algorithm for finding strongly connected components
- Planar Strong Connectivity Helps in Parallel Depth-First Search
- Finding strongly connected components in distributed graphs
- Solving multi-agent path finding on strongly biconnected digraphs
- Finding strongly connected components of simple digraphs based on granulation strategy
- Strong-mixed searching and pathwidth
- Finding biconnected components in O(n) time for a class of graphs
- scientific article; zbMATH DE number 1942448
- A stabilizing algorithm for finding biconnected components
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Depth-First Search and Linear Graph Algorithms
- Title not available (Why is that?)
- Efficient Planarity Testing
- Efficiency of a Good But Not Linear Set Union Algorithm
- A linear-time algorithm for a special case of disjoint set union
- A strong-connectivity algorithm and its applications in data flow analysis
- On the computational power of pushdown automata
- Title not available (Why is that?)
- Parallel concepts in graph theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Time and tape complexity of pushdown automaton languages
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- Path-based depth-first search for strong and biconnected components
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dividing a Graph into Triconnected Components
- Cycle Length in a Random Function
Cited In (29)
- Computing finite semigroups
- \(\Delta \)-list vertex coloring in linear time
- On the complexity of strongly connected components in directed hypergraphs
- 4-edge-coloring graphs of maximum degree 3 in linear time
- Finding strong components using depth-first search
- Deriving efficient graph algorithms
- Yet another optimal algorithm for 3-edge-connectivity
- Enumeration of idempotents in planar diagram monoids
- Verification of programs with exceptions through operator precedence automata
- Stubborn Sets, Frozen Actions, and Fair Testing
- Notes on oriented depth-first search and longest paths
- Path-based depth-first search for strong and biconnected components
- Computing maximal subsemigroups of a finite semigroup
- The scaling limit of a critical random directed graph
- Fault tolerant depth first search in undirected graphs: simple yet efficient
- A space-efficient algorithm for finding strongly connected components
- An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
- Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
- An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
- Space efficient linear time algorithms for BFS, DFS and applications
- Separator-based data reduction for signed graph balancing
- An analysis of repeated graph search
- Finding strongly connected components of simple digraphs based on granulation strategy
- Title not available (Why is that?)
- A simple certifying algorithm for 3-edge-connectivity
- Title not available (Why is that?)
- Space-efficient biconnected components and recognition of outerplanar graphs
Uses Software
This page was built for publication: Path-based depth-first search for strong and biconnected components
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294748)
