Algorithm suggestion: st-orientation algorithm(s) #7346
jar2333
started this conversation in
Algorithms
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
-
A few years ago, I explored st-orientations (also called bipolar orientations) and implemented an algorithm by C. Papamanthou and I. G. Tollis for computing a parameterized st-orientation of a given graph, using networkx. In their algorithm, the parameter p controls the length of the longest path. I have reviewed the mathematical literature to understand properties of st-orientations, such as H. Fraysseix et al. I would love to contribute a set of st-orientation algorithms, including the one from C. Papamanthou and I. G. Tollis, but also simpler non-parameterized algorithms. A review on applications of st-orientations can be found in this paper.
My prior implementation is amateurish, but I can revisit it and reimplement it following Python and NetworkX best practices, and by leveraging standard data structures/algorithms.
Beta Was this translation helpful? Give feedback.
All reactions