Geodesic
Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time
Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 3, pp. 325-346.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis in weighted partial 2-trees (i.e., graphs of treewidth at most two) with non-negative edge-weights. The implicit representation can be made explicit in a running time that is proportional to the size of the minimum cycle basis. For planar graphs, Borradaile, Sankowski, and Wulff-Nilsen [Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time, FOCS 2010] showed how to compute an implicit O(n logn) space representation of an minimum cycle basis in O(n log5 n) time. For the special case of partial 2-trees, our algorithm improves this result to linear time and space. Such an improvement was achieved previously only for outerplanar graphs [Liu and Lu: Minimum Cycle Bases of Weighted Outerplanar Graphs, IPL 110:970-974, 2010] 
@article{JGAA_2014_18_3_a1,
     author = {Carola Doerr and G. Ramakrishna and Jens Schmidt},
     title = {Computing {Minimum} {Cycle} {Bases} in {Weighted} {Partial} {2-Trees} in {Linear} {Time}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {325--346},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2014},
     doi = {10.7155/jgaa.00325},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00325/}
}
TY  - JOUR
AU  - Carola Doerr
AU  - G. Ramakrishna
AU  - Jens Schmidt
TI  - Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 325
EP  - 346
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00325/
DO  - 10.7155/jgaa.00325
LA  - en
ID  - JGAA_2014_18_3_a1
ER  - 
%0 Journal Article
%A Carola Doerr
%A G. Ramakrishna
%A Jens Schmidt
%T Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time
%J Journal of Graph Algorithms and Applications
%D 2014
%P 325-346
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00325/
%R 10.7155/jgaa.00325
%G en
%F JGAA_2014_18_3_a1
Carola Doerr; G. Ramakrishna; Jens Schmidt. Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time. Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 3, pp. 325-346. doi : 10.7155/jgaa.00325. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00325/

Cité par Sources :