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

DOI10.1016/J.IPL.2003.07.003MaRDI QIDQ1029002zbMATH OpenOpenAlexFDO

Authors 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

algorithmsapproximation algorithmscombinatorial problemscomputational complexitycycle basis

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2080984
• Approximation and Online Algorithms
• On finding a cycle basis with a shortest maximal cycle
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• On the approximability of the minimum strictly fundamental cycle basis problem

Cites work

• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• scientific article; zbMATH DE number 1532269 (Why is no real title available?)
• scientific article; zbMATH DE number 4121482 (Why is no real title available?)
• On cycle bases of a graph
• On finding a cycle basis with a shortest maximal cycle
• On Optimum Cycle Bases

Cited in

(13)

• Minimum weakly fundamental cycle bases are hard to find
• On finding a cycle basis with a shortest maximal cycle
• The minimum stretch spanning tree problem for typical graphs
• Hardness and efficiency on \(t\)-admissibility for graph operations
• The zoo of tree spanner problems
• Optimality computation of the minimum stretch spanning tree problem
• Counting 2-connected deletion-minors of binary matroids
• scientific article; zbMATH DE number 2080984 (Why is no real title available?)
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• An improved heuristic for computing short integral cycle bases
• Approximation and Online Algorithms
• Tree 3-spanners on generalized prisms of graphs
• On the approximability of the minimum strictly fundamental cycle basis problem

This page was built for publication: On finding cycle bases and fundamental cycle bases with a shortest maximal cycle

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