Minimum weakly fundamental cycle bases are hard to find

DOI10.1007/S00453-007-9112-8zbMATH Open1172.68026DBLPjournals/algorithmica/Rizzi09OpenAlexW1972660489WikidataQ56020351 ScholiaQ56020351MaRDI QIDQ1024786FDOQ1024786

Romeo Rizzi

Publication date: 17 June 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9112-8

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

zbMATH Keywords

computational complexitygraphscombinatorial optimizationapproximation algorithmminimum cycle basis problemfundamental cycle basisweakly fundamental cycle basis

Mathematics Subject Classification ID

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)

Cites Work

• Some APX-completeness results for cubic graphs
• Title not available (Why is that?)
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Algorithms for Generating Fundamental Cycles in a Graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Minimum cycle bases for network graphs
• Title not available (Why is that?)
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Title not available (Why is that?)
• Automata, Languages and Programming
• Algorithms - ESA 2003
• The NP-Completeness of Some Edge-Partition Problems
• On the Abstract Properties of Linear Dependence
• Packing cycles in undirected graphs
• A greedy approach to compute a minimum cycle basis of a directed graph
• New length bounds for cycle bases
• Title not available (Why is that?)
• Title not available (Why is that?)
• STACS 2005
• Classes of cycle bases
• Algorithms for finding minimum fundamental cycle bases in graphs
• Approximation and Online Algorithms
• Hypothetical complexity of the nowhere-zero 5-flow problem

Cited In (13)

• Minimum strictly fundamental cycle bases of planar graphs are hard to find
• Rooted Cycle Bases
• Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
• Target set selection for conservative populations
• New approximation algorithms for minimum cycle bases of graphs
• Minimum Cycle Bases and Their Applications
• Cycle-based cluster variational method for direct and inverse inference
• Classes of cycle bases
• Properties of Gomory-Hu co-cycle bases
• On a Special Co-cycle Basis of Graphs
• Robust cycle bases do not exist for \(K_{n, n}\) if \(n \geq 8\)
• Integral cycle bases for cyclic timetabling
• Benchmarks for Strictly Fundamental Cycle Bases

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)