Lower bounds for strictly fundamental cycle bases in grid graphs

DOI10.1002/net.20283zbMath1167.05049OpenAlexW4247370028MaRDI QIDQ5191140

Romeo Rizzi, Gregor Wünsch, Christian Liebchen, Ekkehard Köhler

Publication date: 28 July 2009

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20283

zbMATH Keywords

combinatorial optimizationasymptotic analysisspanning treeminimum cycle basisplanar dual

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Cycle bases in graphs characterization, algorithms, complexity, and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classes of cycle bases
• Graph minors. V. Excluding a planar graph
• New length bounds for cycle bases
• The zoo of tree spanner problems
• Algorithms for Generating Fundamental Cycles in a Graph
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• On the Abstract Properties of Linear Dependence
• Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases
• Algorithms for finding a fundamental set of cycles for an undirected linear graph
• An algorithm for finding a fundamental set of cycles of a graph