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...
| Autor principal: | |
|---|---|
| Formato: | Artículo |
| Lenguaje: | English |
| Publicado: |
Discrete Mathematics & Theoretical Computer Science
2004-01-01
|
| Colección: | Discrete Mathematics & Theoretical Computer Science |
| Materias: | |
| Acceso en línea: | https://dmtcs.episciences.org/314/pdf |