Algorithms for Generating Fundamental Cycles in a Graph

DOI10.1145/355984.355988zbMath0477.68070OpenAlexW1984040953MaRDI QIDQ3933763

Narsingh Deo, G. M. Prabhu, Mukkai S. Krishnamoorthy

Publication date: 1982

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/355984.355988

zbMATH Keywords

spanning treeNP-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (37)

Minimum strictly fundamental cycle bases of planar graphs are hard to find ⋮ The Dual Variable Method for the Solution of Compressible Fluid Flow Problems ⋮ On finding a cycle basis with a shortest maximal cycle ⋮ New length bounds for cycle bases ⋮ On the stability properties of linear dynamic time-varying unforced systems involving switches between parameterizations from topologic considerations via graph theory ⋮ A null-space approach for large-scale symmetric saddle point systems with a small and non zero \((2, 2)\) block ⋮ Sparse null basis computations in structural optimization ⋮ Classes of cycle bases ⋮ Minimum spanning tree cycle intersection problem ⋮ The Null Space Problem I. Complexity ⋮ Perfect hashing ⋮ Distance geometry and data science ⋮ Cycle-based formulations in distance geometry ⋮ On the approximability of the minimum strictly fundamental cycle basis problem ⋮ Minimum spanning tree cycle intersection problem on outerplanar graphs ⋮ The Null Space Problem II. Algorithms ⋮ The Hamilton spaces of Cayley graphs on abelian groups ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ Advances in metric embedding theory ⋮ On minimum average stretch spanning trees in grid graphs ⋮ Modeling the dynamics of complex multibody systems with kinematical transmission elements ⋮ The zoo of tree spanner problems ⋮ Algorithmic parameterization of mixed treatment comparisons ⋮ Minimum cut bases in undirected networks ⋮ Lower bounds for strictly fundamental cycle bases in grid graphs ⋮ An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs ⋮ Integral cycle bases for cyclic timetabling ⋮ Edge-swapping algorithms for the minimum fundamental cycle basis problem ⋮ A cycle-based formulation for the distance geometry problem ⋮ Minimum Cycle Bases and Their Applications ⋮ Minimum weakly fundamental cycle bases are hard to find ⋮ Characterizing attitudinal network graphs through frustration cloud ⋮ Properties of Gomory-Hu co-cycle bases ⋮ Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion ⋮ On minimum average stretch spanning trees in polygonal 2-trees ⋮ On Optimum Cycle Bases ⋮ Algorithms for finding minimum fundamental cycle bases in graphs

This page was built for publication: Algorithms for Generating Fundamental Cycles in a Graph