Computing minimum cycle bases in weighted partial 2-trees in linear time

DOI10.1007/978-3-642-45043-3_20MaRDI QIDQ2864304zbMATH OpenOpenAlexFDO

Authors Carola Doerr, G. Ramakrishna, Jens M. Schmidt

Publication date 6 December 2013

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.0728

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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. Our algorithm improves the result of Borradaile, Sankowski, and Wulff-Nilsen [Min $st$-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time, FOCS 2010]---which computes for all planar graphs an implicit $O(nlogn)$ space representation of an MCB in $O(nlo{g}^{5}n)$ time---by a polylog factor for the special case of partial 2-trees. 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].

Recommendations

• Computing minimum cycle bases in weighted partial 2-trees in linear time
• Characterization of minimum cycle basis in weighted partial 2-trees
• Minimum cycle bases of weighted outerplanar graphs
• Minimum cycle bases of weighted outerplanar graphs
• An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs

Cited in

(3)

• Characterization of minimum cycle basis in weighted partial 2-trees
• Computing minimum cycle bases in weighted partial 2-trees in linear time
• Find subtrees of specified weight and cycles of specified length in linear time

This page was built for publication: Computing minimum cycle bases in weighted partial 2-trees in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2864304)