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

DOI10.1016/j.dam.2015.12.001zbMath1333.05153OpenAlexW2208043519MaRDI QIDQ266952

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-completenessplanar graphminimum strictly fundamental cycle basis

Mathematics Subject Classification ID

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

Related Items (2)

Minimum spanning tree cycle intersection problem on outerplanar graphs ⋮ On minimum average stretch spanning trees in grid graphs

Cites Work

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

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