On finding cycle bases and fundamental cycle bases with a shortest maximal cycle

DOI10.1016/j.ipl.2003.07.003zbMath1178.68679OpenAlexW2002038988MaRDI QIDQ1029002

Giulia Galbiati

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.07.003

zbMATH Keywords

algorithmscomputational complexitycombinatorial problemsapproximation algorithmscycle basis

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Optimality computation of the minimum stretch spanning tree problem ⋮ Counting 2-connected deletion-minors of binary matroids ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ Hardness and efficiency on \(t\)-admissibility for graph operations ⋮ The zoo of tree spanner problems ⋮ The minimum stretch spanning tree problem for typical graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On finding a cycle basis with a shortest maximal cycle
• On cycle bases of a graph
• On Optimum Cycle Bases
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph