Geodesic
Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs
Discrete mathematics & theoretical computer science, Tome 6 (2003-2004) no. 2.

Voir la notice de l'article provenant de la source Episciences

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 vertices and bridges of a trapezoid graph, assuming the trapezoid diagram is given. Our algorithms can be easily parallelized on the EREW PRAM computational model so that cut vertices and bridges can be found in O(log n) time by using O(n / log n) processors. 
@article{DMTCS_2004_6_2_a5,
     author = {Chen, Hon-Chan},
     title = {Optimal {Sequential} and {Parallel} {Algorithms} for {Cut} {Vertices} and {Bridges} on {Trapezoid} {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {6},
     number = {2},
     year = {2003-2004},
     doi = {10.46298/dmtcs.314},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.314/}
}
TY  - JOUR
AU  - Chen, Hon-Chan
TI  - Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2003-2004
VL  - 6
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.314/
DO  - 10.46298/dmtcs.314
LA  - en
ID  - DMTCS_2004_6_2_a5
ER  - 
%0 Journal Article
%A Chen, Hon-Chan
%T Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs
%J Discrete mathematics & theoretical computer science
%D 2003-2004
%V 6
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.314/
%R 10.46298/dmtcs.314
%G en
%F DMTCS_2004_6_2_a5
Chen, Hon-Chan. Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs. Discrete mathematics & theoretical computer science, Tome 6 (2003-2004) no. 2. doi : 10.46298/dmtcs.314. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.314/

Cité par Sources :