Minimum strictly fundamental cycle bases of planar graphs are hard to find
From MaRDI portal
Publication:266952
DOI10.1016/j.dam.2015.12.001zbMath1333.05153OpenAlexW2208043519MaRDI QIDQ266952
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
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