A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs

DOI10.1007/11786986_23zbMATH Open1223.05298OpenAlexW2129660997MaRDI QIDQ3613764FDOQ3613764

Authors: Ramesh Hariharan, Telikepalli Kavitha, K. Mehlhorn 

Publication date: 12 March 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11786986_23

Recommendations

• Faster Algorithms for Minimum Cycle Basis in Directed Graphs
• Automata, Languages and Programming
• Algorithms to compute minimum cycle basis in directed graphs
• STACS 2005
• Breaking the O(m 2 n) Barrier for Minimum Cycle Bases

zbMATH Keywords

directed graphminimum cycle basis

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Nonnumerical algorithms (68W05) Paths and cycles (05C38)

Cited In (14)

• Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Algorithms to compute minimum cycle basis in directed graphs
• New approximation algorithms for minimum cycle bases of graphs
• Title not available (Why is that?)
• Automata, Languages and Programming
• Title not available (Why is that?)
• An \(O(nm)\) time algorithm for finding the min length directed cycle in a graph
• Forward and line-based cycle bases for periodic timetabling
• STACS 2005
• Faster Algorithms for Minimum Cycle Basis in Directed Graphs
• A greedy approach to compute a minimum cycle basis of a directed graph
• On a Special Co-cycle Basis of Graphs
• Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs

This page was built for publication: A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3613764)