New approximation algorithms for minimum cycle bases of graphs
From MaRDI portal
Publication:633843
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
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
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 2 ) 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
