Minimum strictly fundamental cycle bases of planar graphs are hard to find

DOI10.1016/J.DAM.2015.12.001MaRDI QIDQ266952zbMATH OpenOpenAlexFDO

Authors Alexander Reich

Publication date 7 April 2016

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

Full work available at URL https://doi.org/10.1016/j.dam.2015.12.001

zbMATH Keywords

NP-completenessminimum strictly fundamental cycle basisplanar graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Recommendations

• On the approximability of the minimum strictly fundamental cycle basis problem
• Benchmarks for Strictly Fundamental Cycle Bases
• scientific article; zbMATH DE number 2080984
• Approximation and Online Algorithms
• Classes of cycle bases

Cites work

• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• A linear algorithm for embedding planar graphs using PQ-trees
• Algorithms for Generating Fundamental Cycles in a Graph
• An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs
• An improved heuristic for computing short integral cycle bases
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs
• Graph theory
• Minimum weakly fundamental cycle bases are hard to find
• New approximation algorithms for minimum cycle bases of graphs
• On the approximability of the minimum strictly fundamental cycle basis problem
• Periodic Timetable Optimization in Public Transport
• Planar 3DM is NP-complete

Cited in

(6)

• Minimum weakly fundamental cycle bases are hard to find
• Minimum spanning tree cycle intersection problem on outerplanar graphs
• Lower bounds for strictly fundamental cycle bases in grid graphs
• scientific article; zbMATH DE number 5257389 (Why is no real title available?)
• On minimum average stretch spanning trees in grid graphs
• Benchmarks for Strictly Fundamental Cycle Bases

This page was built for publication: Minimum strictly fundamental cycle bases of planar graphs are hard to find

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