A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
From MaRDI portal
Publication:3769979
DOI10.1137/0216026zbMATH Open0632.68064OpenAlexW1966878439MaRDI QIDQ3769979FDOQ3769979
Authors: J. D. Horton 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Paths and cycles (05C38)
Cited In (83)
- The zoo of tree spanner problems
- Minimum cut bases in undirected networks
- Minimum strictly fundamental cycle bases of planar graphs are hard to find
- Minimum cycle bases of graphs over different fields
- On Optimum Cycle Bases
- On finding cycle bases and fundamental cycle bases with a shortest maximal cycle
- Cycle bases in graphs characterization, algorithms, complexity, and applications
- Edge-swapping algorithms for the minimum fundamental cycle basis problem
- The cycle's structure of embedded graphs in surfaces
- On the approximability of the minimum strictly fundamental cycle basis problem
- New approximation algorithms for minimum cycle bases of graphs
- On finding a cycle basis with a shortest maximal cycle
- Minimum cycle bases of direct products of complete graphs
- RELEVANT CYCLES IN CHEMICAL REACTION NETWORKS
- Approximate inverse Ising models close to a Bethe reference point
- An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs
- Minimum weakly fundamental cycle bases are hard to find
- Efficient approximation algorithms for shortest cycles in undirected graphs
- Short cycle structures for graphs on surfaces and an open problem of Mohar and Thomassen
- Minor and minimum cycle bases of a 3-connected planar graph
- On the automation of the force method in the optimal plastic design of frames
- Minimum Cycle Bases and Their Applications
- Factoring with Two Large Primes
- Minimum cycle bases of graphs on surfaces
- Minimum fundamental cycle basis of some bipartite graphs
- Testing connectivity of faulty networks in sublinear time
- Title not available (Why is that?)
- Algorithms for shortest paths and \(d\)-cycle problems
- Forward and line-based cycle bases for periodic timetabling
- Generating cycle spaces for graphs on surfaces with small genera
- On the Complexity of Matroid Isomorphism Problems
- Modeling the dynamics of complex multibody systems with kinematical transmission elements
- The Null Space Problem II. Algorithms
- When do short cycles generate the cycle space?
- Cycle-based cluster variational method for direct and inverse inference
- Classes of cycle bases
- A greedy approach to compute a minimum cycle basis of a directed graph
- Properties of Gomory-Hu co-cycle bases
- On a Special Co-cycle Basis of Graphs
- On the complexity of matroid isomorphism problem
- Certifying algorithms
- On the role of differential adhesion in gangliogenesis in the enteric nervous system
- Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
- To approximate treewidth, use treelength!
- Integral cycle bases for cyclic timetabling
- Characterization of minimum cycle basis in weighted partial 2-trees
- Computing sharp recovery structures for locally recoverable codes
- Structural stability and jamming of self-organized cluster conformations in dense granular materials
- A redundancy eliminating approach to linearly independent rings selection in the ring perception problem
- A note on finding a shortest complete cycle in an undirected graph
- Title not available (Why is that?)
- New length bounds for cycle bases
- Finding a shortest cycle in a subspace of the cycle space of a graph
- Title not available (Why is that?)
- Short cycle structure of graphs on surfaces. I: The uniqueness theorems
- Counting 2-connected deletion-minors of binary matroids
- Sparse null basis computations in structural optimization
- Minimum cycle bases of weighted outerplanar graphs
- Finding short cycles in embedded graph in polynomial time
- A null-space approach for large-scale symmetric saddle point systems with a small and non zero \((2, 2)\) block
- Cycle analysis of directed acyclic graphs
- Suboptimal cycle bases for the force method
- Canonical sphere bases for simplicial and cubical complexes
- Length bounds for cycle bases of graphs
- Minimum cycle basis of direct product of \(K_2 \times K_n\)
- Minimum spanning tree cycle intersection problem on outerplanar graphs
- Finding shorter cycles in a weighted graph
- Minimal cycle basis of graph products for the force method of frame analysis
- Subminimal cycle basis of a graph for efficient force method of frame analysis
- All Circuits Enumeration in Macro-Econometric Models
- Recovering a magnitude-symmetric matrix from its principal minors
- Analysis of frames by substructuring technique based on using algebraic and graph methods
- Revised Greedy algorithm for formation of a minimal cycle basis of a graph
- A cycle-based formulation for the distance geometry problem
- Title not available (Why is that?)
- Rooted cycle bases
- Building stable chains with motile agents: insights into the morphology of enteric neural crest cell migration
- Minimum spanning tree cycle intersection problem
- Flow and Elastic Networks on the 𝑛-Torus: Geometry, Analysis, and Computation
- Cycle-based formulations in distance geometry
- Suboptimal cycle bases of graphs using ant colony system algorithm
- The Steinberg module of a graph
- Spectral synchronization of multiple views in \(\mathrm{SE}(3)\)
This page was built for publication: A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3769979)
