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

Publikationstyp
Conference Paper
Date Issued
2013
Sprache
English
Author(s)
Doerr, Carola  
Ramakrishna, G.  
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7634
First published in
Lecture notes in computer science  
Number in series
8165 LNCS
Start Page
225
End Page
236
Citation
39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013)
Contribution to Conference
39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013)  
Publisher DOI
10.1007/978-3-642-45043-3_20
Scopus ID
2-s2.0-84893132436
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].
DDC Class
004: Informatik