Minimum weakly fundamental cycle bases are hard to find

DOI10.1007/s00453-007-9112-8zbMath1172.68026OpenAlexW1972660489WikidataQ56020351 ScholiaQ56020351MaRDI QIDQ1024786

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

zbMATH Keywords

computational complexitycombinatorial optimizationapproximation algorithmgraphsminimum cycle basis problemfundamental cycle basisweakly fundamental cycle basis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (10)

Minimum strictly fundamental cycle bases of planar graphs are hard to find ⋮ Rooted Cycle Bases ⋮ Cycle-based cluster variational method for direct and inverse inference ⋮ On a Special Co-cycle Basis of Graphs ⋮ New approximation algorithms for minimum cycle bases of graphs ⋮ Target set selection for conservative populations ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ Integral cycle bases for cyclic timetabling ⋮ Minimum Cycle Bases and Their Applications ⋮ Properties of Gomory-Hu co-cycle bases

Cites Work

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

This page was built for publication: Minimum weakly fundamental cycle bases are hard to find