New length bounds for cycle bases

DOI10.1016/j.ipl.2007.06.013zbMath1185.05086OpenAlexW2086012735MaRDI QIDQ2380021

Christian Liebchen, Romeo Rizzi, Michael Elkin

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://depositonce.tu-berlin.de/handle/11303/15619

zbMATH Keywords

graph algorithmsapproximation algorithmsmetric approximationcycle bases

Mathematics Subject Classification ID

Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Approximation algorithms (68W25)

Related Items

Rooted Cycle Bases ⋮ New length bounds for cycle bases ⋮ On a Special Co-cycle Basis of Graphs ⋮ Minimum spanning tree cycle intersection problem on outerplanar graphs ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ Volume in general metric spaces ⋮ Advances in metric embedding theory ⋮ Lower bounds for strictly fundamental cycle bases in grid graphs ⋮ Edge-swapping algorithms for the minimum fundamental cycle basis problem ⋮ Minimum Cycle Bases and Their Applications ⋮ Minimum weakly fundamental cycle bases are hard to find ⋮ Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion ⋮ Flow and Elastic Networks on the 𝑛-Torus: Geometry, Analysis, and Computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• New length bounds for cycle bases
• All-Pairs Small-Stretch Paths
• Minimum cycle bases
• Lower-stretch spanning trees
• New Approximation Algorithms for Minimum Cycle Bases of Graphs
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Algorithms for Generating Fundamental Cycles in a Graph
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Automata, Languages and Programming
• Algorithms - ESA 2003
• A tight bound on approximating arbitrary metrics by tree metrics