A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs

DOI10.1007/11786986_23MaRDI QIDQ3613764zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(14)

• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
• Algorithms to compute minimum cycle basis in directed graphs
• New approximation algorithms for minimum cycle bases of graphs
• scientific article; zbMATH DE number 7204576 (Why is no real title available?)
• Automata, Languages and Programming
• scientific article; zbMATH DE number 7760193 (Why is no real title available?)
• 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)