Applications of LexDFS.
- Linear Time LexDFS on Cocomparability Graphs
https://arxiv.org/abs/1404.5996
also described here:
Efficient Algorithms on Cocomparability Graphs via Vertex Orderings
https://tspace.library.utoronto.ca/handle/1807/92081
file: cc_linear_lexdfs.py
Problems:- creating umbrella-free ordering is not implemented
the way to do it can be found here:
Modular decompositionand transitive orientation
https://www.sciencedirect.com/science/article/pii/S0012365X98003197
or here
Simpler, Linear-Time Transitive Orientation via Lexicographic Breadth-First Search
https://arxiv.org/abs/1503.02773
- creating umbrella-free ordering is not implemented