A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
From MaRDI portal
Publication:3769979
DOI10.1137/0216026zbMath0632.68064OpenAlexW1966878439MaRDI QIDQ3769979
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0216026
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)
Related Items
Minimum strictly fundamental cycle bases of planar graphs are hard to find, The cycle's structure of embedded graphs in surfaces, Cycle analysis of directed acyclic graphs, Length bounds for cycle bases of graphs, Generating cycle spaces for graphs on surfaces with small genera, Rooted Cycle Bases, A redundancy eliminating approach to linearly independent rings selection in the ring perception problem, Minimum cycle bases of direct products of complete graphs, On finding a cycle basis with a shortest maximal cycle, New length bounds for cycle bases, All Circuits Enumeration in Macro-Econometric Models, Cycle-based cluster variational method for direct and inverse inference, Short cycle structures for graphs on surfaces and an open problem of Mohar and Thomassen, 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, On the automation of the force method in the optimal plastic design of frames, Minimum spanning tree cycle intersection problem, Structural stability and jamming of self-organized cluster conformations in dense granular materials, Algorithms for shortest paths and \(d\)-cycle problems, Revised Greedy algorithm for formation of a minimal cycle basis of a graph, Minimum cycle bases of weighted outerplanar graphs, Counting 2-connected deletion-minors of binary matroids, Building stable chains with motile agents: insights into the morphology of enteric neural crest cell migration, Canonical sphere bases for simplicial and cubical complexes, Cycle-based formulations in distance geometry, On the approximability of the minimum strictly fundamental cycle basis problem, Forward and line-based cycle bases for periodic timetabling, On a Special Co-cycle Basis of Graphs, Minimum spanning tree cycle intersection problem on outerplanar graphs, New approximation algorithms for minimum cycle bases of graphs, The Null Space Problem II. Algorithms, On the complexity of matroid isomorphism problem, Minimal cycle basis of graph products for the force method of frame analysis, Testing connectivity of faulty networks in sublinear time, Cycle bases in graphs characterization, algorithms, complexity, and applications, Analysis of frames by substructuring technique based on using algebraic and graph methods, Certifying algorithms, Approximate inverse Ising models close to a Bethe reference point, Finding a shortest cycle in a subspace of the cycle space of a graph, Characterization of minimum cycle basis in weighted partial 2-trees, Minimum cycle bases of graphs on surfaces, Subminimal cycle basis of a graph for efficient force method of frame analysis, Minimum fundamental cycle basis of some bipartite graphs, Suboptimal cycle bases of graphs using ant colony system algorithm, Short cycle structure of graphs on surfaces. I: The uniqueness theorems, Modeling the dynamics of complex multibody systems with kinematical transmission elements, The zoo of tree spanner problems, Minimum cycle basis of direct product of \(K_2 \times K_n\), Minimum cut bases in undirected networks, To Approximate Treewidth, Use Treelength!, Efficient approximation algorithms for shortest cycles in undirected graphs, On the role of differential adhesion in gangliogenesis in the enteric nervous system, Factoring with Two Large Primes, RELEVANT CYCLES IN CHEMICAL REACTION NETWORKS, Finding shorter cycles in a weighted graph, Efficient Approximation Algorithms for Shortest Cycles in Undirected 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, Suboptimal cycle bases for the force method, A cycle-based formulation for the distance geometry problem, Minimum Cycle Bases and Their Applications, On the Complexity of Matroid Isomorphism Problems, Minimum weakly fundamental cycle bases are hard to find, On finding cycle bases and fundamental cycle bases with a shortest maximal cycle, Properties of Gomory-Hu co-cycle bases, The Steinberg module of a graph, Minor and minimum cycle bases of a 3-connected planar graph, A greedy approach to compute a minimum cycle basis of a directed graph, Computing sharp recovery structures for locally recoverable codes, On Optimum Cycle Bases, Minimum cycle bases of graphs over different fields, Spectral Synchronization of Multiple Views in SE(3), Flow and Elastic Networks on the 𝑛-Torus: Geometry, Analysis, and Computation
