Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time | Zendy

Carola Doerr | Zendy; G. Ramakrishna | Zendy; Jens M. Schmidt | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time

Author(s) -

Carola Doerr,

G. Ramakrishna,

Jens M. Schmidt

Publication year - 2014

Publication title -

journal of graph algorithms and applications

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.387

H-Index - 38

ISSN - 1526-1719

DOI - 10.7155/jgaa.00325

Subject(s) - treewidth , cycle basis , representation (politics) , mathematics , running time , basis (linear algebra) , time complexity , linear space , combinatorics , computer science , discrete mathematics , graph , algorithm , pathwidth , geometry , line graph , politics , political science , law , graph power

International audienceWe 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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research