Filters

2013 - 201922020 - 20211

Settings

Now showing1 - 3 of 3
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: without files ,
      183
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: without files ,
    Computing minimum cycle bases in weighted partial 2-trees in linear time
    (2014)
    Doerr, Carola
    ;
    Ramakrishna, G.
    ;
    Schmidt, Jens M.
    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 log n) space representation of an minimum cycle basis in O(n log5 n) time. For the special case of par-tial 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].
    Publicationtype: Journal Article
      82
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: without files ,
    Computing minimum cycle bases in weighted partial 2-trees in linear time
    (2013)
    Doerr, Carola
    ;
    Ramakrishna, G.
    ;
    Schmidt, Jens M.
    We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis (MCB) in weighted partial 2-trees, i.e., graphs of treewidth two. The implicit representation can be made explicit in a running time that is proportional to the size of the MCB. 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 MCB 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].
    Publicationtype: Conference Paper
      49