Minimum weakly fundamental cycle bases are hard to find
From MaRDI portal
Publication:1024786
computational complexitygraphscombinatorial optimizationapproximation algorithmminimum cycle basis problemfundamental cycle basisweakly fundamental cycle basis
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)
Recommendations
- Minimum strictly fundamental cycle bases of planar graphs are hard to find
- On finding cycle bases and fundamental cycle bases with a shortest maximal cycle
- Minimum Cycle Bases and Their Applications
- On the approximability of the minimum strictly fundamental cycle basis problem
- Minimum cycle bases of graphs over different fields
- Approximation and Online Algorithms
- scientific article; zbMATH DE number 2080984
- Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases
- Minimum fundamental cycle basis of some bipartite graphs
- Algorithms for finding minimum fundamental cycle bases in graphs
Cites work
- scientific article; zbMATH DE number 2089223 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1943957 (Why is no real title available?)
- scientific article; zbMATH DE number 3001191 (Why is no real title available?)
- scientific article; zbMATH DE number 1775400 (Why is no real title available?)
- scientific article; zbMATH DE number 2123255 (Why is no real title available?)
- scientific article; zbMATH DE number 3215864 (Why is no real title available?)
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
- A greedy approach to compute a minimum cycle basis of a directed graph
- Algorithms for Generating Fundamental Cycles in a Graph
- Algorithms for finding minimum fundamental cycle bases in graphs
- Approximation and Online Algorithms
- Automata, Languages and Programming
- Classes of cycle bases
- Finding short integral cycle bases for cyclic timetabling
- Hypothetical complexity of the nowhere-zero 5-flow problem
- Inapproximability of combinatorial optimization problems
- Minimum cycle bases for network graphs
- New length bounds for cycle bases
- On the Abstract Properties of Linear Dependence
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- Packing cycles in undirected graphs
- STACS 2005
- Some APX-completeness results for cubic graphs
- The NP-Completeness of Some Edge-Partition Problems
Cited in
(13)- Properties of Gomory-Hu co-cycle bases
- On a Special Co-cycle Basis of Graphs
- Integral cycle bases for cyclic timetabling
- Robust cycle bases do not exist for \(K_{n, n}\) if \(n \geq 8\)
- Target set selection for conservative populations
- New approximation algorithms for minimum cycle bases of graphs
- Cycle-based cluster variational method for direct and inverse inference
- Rooted cycle bases
- Classes of cycle bases
- Minimum strictly fundamental cycle bases of planar graphs are hard to find
- Minimum Cycle Bases and Their Applications
- Benchmarks for Strictly Fundamental Cycle Bases
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
This page was built for publication: Minimum weakly fundamental cycle bases are hard to find
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024786)
