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

DOI10.1016/J.DAM.2015.12.001zbMATH Open1333.05153OpenAlexW2208043519MaRDI QIDQ266952FDOQ266952

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

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

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)

Cites Work

• Graph theory
• Title not available (Why is that?)
• 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
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Periodic Timetable Optimization in Public Transport
• An improved heuristic for computing short integral cycle bases
• On the approximability of the minimum strictly fundamental cycle basis problem
• New approximation algorithms for minimum cycle bases of graphs

Cited In (6)

• Minimum weakly fundamental cycle bases are hard to find
• Title not available (Why is that?)
• Lower bounds for strictly fundamental cycle bases in grid graphs
• Minimum spanning tree cycle intersection problem on outerplanar graphs
• 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)