Minimum cycle bases for network graphs

DOI10.1007/S00453-004-1098-XMaRDI QIDQ1882477zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Franziska Berger, Peter Gritzmann, Sven De Vries

Publication date 1 October 2004

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-004-1098-x

zbMATH Keywords

Electrical networkGraph cycleMatroidMinimum cycle basis

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Minimum cycle bases, faster and simpler
• An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs
• Minimum Cycle Bases in Graphs Algorithms and Applications
• Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs
• Experimental and Efficient Algorithms

Cited in

(33)

• Integral cycle bases for cyclic timetabling
• Minimum weakly fundamental cycle bases are hard to find
• A greedy approach to compute a minimum cycle basis of a directed graph
• On finding a cycle basis with a shortest maximal cycle
• Union of all the minimum cycle bases of a graph
• Length bounds for cycle bases of graphs
• Minimum cycle bases of weighted outerplanar graphs
• Minimum cycle bases of graphs on surfaces
• Minimum spanning tree cycle intersection problem
• Stratified sampling for the Ising model: A graph-theoretic approach
• Minimum path bases and relevant paths
• Tomography on Finite Graphs
• Minimum cycle bases of graphs over different fields
• On optimal cycle bases of graphs for mesh analysis of networks
• On a Special Co-cycle Basis of Graphs
• Minimum Cycle Bases in Graphs Algorithms and Applications
• Minimum Cycle Bases and Their Applications
• scientific article; zbMATH DE number 4010557 (Why is no real title available?)
• scientific article; zbMATH DE number 2080984 (Why is no real title available?)
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• The minimum fundamental cycle basic problem: a new heuristic based on edge swaps
• Suboptimal cycle bases of graphs using ant colony system algorithm
• Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases
• scientific article; zbMATH DE number 1405805 (Why is no real title available?)
• The minimal cycle basis of circular graphs
• scientific article; zbMATH DE number 5257389 (Why is no real title available?)
• New approximation algorithms for minimum cycle bases of graphs
• Computing cyclic invariants for molecular graphs
• Cyclic path homology of (di)graphs
• Sensor networks: from dependence analysis via matroid bases to online synthesis
• Algebraic and topological indices of molecular pathway networks in human cancers
• Properties of Gomory-Hu co-cycle bases
• Classes of cycle bases

This page was built for publication: Minimum cycle bases for network graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1882477)