New approximation algorithms for minimum cycle bases of graphs

DOI10.1007/s00453-009-9313-4zbMath1215.68185OpenAlexW2026735029MaRDI QIDQ633843

Dimitrios Michail, Kurt Mehlhorn, Telikepalli Kavitha

Publication date: 30 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://edoc.mpg.de/356750

zbMATH Keywords

cycle spacegraphsapproximation algorithmscycle basisspannersfast matrix multiplication

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Minimum strictly fundamental cycle bases of planar graphs are hard to find ⋮ A direct method for calculating cell cycles of a block map of a simple planar graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classes of cycle bases
• Matrix multiplication via arithmetic progressions
• An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs
• Minimum weakly fundamental cycle bases are hard to find
• A greedy approach to compute a minimum cycle basis of a directed graph
• Classes of graphs which approximate the complete Euclidean graph
• On sparse spanners of weighted graphs
• Minimal cycle bases of outerplanar graphs
• Minimum cycle bases for network graphs
• Algorithms to compute minimum cycle basis in directed graphs
• Approximate distance oracles for unweighted graphs in expected O ( n ² ) time
• Approximate distance oracles
• New Approximation Algorithms for Minimum Cycle Bases of Graphs
• A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Efficient Planarity Testing
• Cycle bases of minimal measure for the structural analysis of skeletal structures by the flexibility method
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• Automata, Languages and Programming
• Automata, Languages and Programming

This page was built for publication: New approximation algorithms for minimum cycle bases of graphs