Characterization of minimum cycle basis in weighted partial 2-trees

DOI10.1016/J.DAM.2014.05.008MaRDI QIDQ491600zbMATH OpenOpenAlexFDO

Authors N. S. Narayanaswamy, G. Ramakrishna

Publication date 18 August 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

partial 2-treeslex short cyclesminimum cycle basis

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22) Paths and cycles (05C38)

Abstract: For a weighted outerplanar graph, the set of lex short cycles is known to be a minimum cycle basis [Inf. Process. Lett. 110 (2010) 970-974 ]. In this work, we show that the set of lex short cycles is a minimum cycle basis in weighted partial 2-trees (graphs of treewidth two) which is a superclass of outerplanar graphs.

Recommendations

• Computing minimum cycle bases in weighted partial 2-trees in linear time
• Minimum cycle bases of weighted outerplanar graphs
• Minimum cycle bases of weighted outerplanar graphs
• Computing minimum cycle bases in weighted partial 2-trees in linear time
• When do short cycles generate the cycle space?

Cites work

• scientific article; zbMATH DE number 3853133 (Why is no real title available?)
• scientific article; zbMATH DE number 3024665 (Why is no real title available?)
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Computing minimum cycle bases in weighted partial 2-trees in linear time
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Minimal cycle bases of outerplanar graphs
• Minimum cycle bases of Halin graphs
• Minimum cycle bases of weighted outerplanar graphs
• On Vector Spaces Associated with a Graph
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs

Cited in

(4)

• Minimum cycle bases of weighted outerplanar graphs
• Computing minimum cycle bases in weighted partial 2-trees in linear time
• Minimum cycle bases of weighted outerplanar graphs
• Computing minimum cycle bases in weighted partial 2-trees in linear time

This page was built for publication: Characterization of minimum cycle basis in weighted partial 2-trees

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