Minimum cycle bases for network graphs

DOI10.1007/s00453-004-1098-xzbMath1082.05083OpenAlexW1966551934WikidataQ61780124 ScholiaQ61780124MaRDI QIDQ1882477

Peter Gritzmann, Franziska Berger, 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

MatroidElectrical networkGraph cycleMinimum cycle basis

Mathematics Subject Classification ID

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

Related Items

Length bounds for cycle bases of graphs ⋮ Stratified sampling for the Ising model: A graph-theoretic approach ⋮ Classes of cycle bases ⋮ Minimum spanning tree cycle intersection problem ⋮ Minimum cycle bases of weighted outerplanar graphs ⋮ On a Special Co-cycle Basis of Graphs ⋮ New approximation algorithms for minimum cycle bases of graphs ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ Minimum cycle bases of graphs on surfaces ⋮ Suboptimal cycle bases of graphs using ant colony system algorithm ⋮ Sensor networks: from dependence analysis via matroid bases to online synthesis ⋮ Algebraic and topological indices of molecular pathway networks in human cancers ⋮ Integral cycle bases for cyclic timetabling ⋮ Minimum Cycle Bases and Their Applications ⋮ Minimum weakly fundamental cycle bases are hard to find ⋮ Properties of Gomory-Hu co-cycle bases ⋮ A greedy approach to compute a minimum cycle basis of a directed graph ⋮ Tomography on Finite Graphs ⋮ Minimum cycle bases of graphs over different fields