Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs
Let G be a graph. A component of G is a maximal connected subgraph in G. A vertex v is a cut vertex of G if k(G-v) > k(G), where k(G) is the number of components in G. Similarly, an edge e is a bridge of G if k(G-e) > k(G). In this paper, we will propose new O(n) algorithms for finding cut ver...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2004-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/314/pdf |