Pre-topological order
In the field of computer science, a pre-topological order or pre-topological ordering of a directed graph is a linear ordering of its vertices such that if there is a directed path from vertex u to vertex v and v comes before u in the ordering, then there is also a directed path from vertex v to vertex u.[1][2]
If the graph is a directed acyclic graph (DAG), topological orderings are pre-topological orderings and vice versa.[1] In other cases, any pre-topological ordering gives a partial order.
References
- ^ a b Schrijver, Alexander (2002-12-10). Combinatorial Optimization: Polyhedra and Efficiency. Springer Science & Business Media. p. 89. ISBN 9783540443896.
- ^ Sedgewick, Robert; Wayne, Kevin (2016-09-26). "Directed Graphs". Algorithms, 4th Edition. Retrieved 2017-09-06.
- v
- t
- e
Sorting algorithms
- Computational complexity theory
- Big O notation
- Total order
- Lists
- Inplacement
- Stability
- Comparison sort
- Adaptive sort
- Sorting network
- Integer sorting
- X + Y sorting
- Transdichotomous model
- Quantum sort
- Bubble sort
- Cocktail shaker sort
- Odd–even sort
- Comb sort
- Gnome sort
- Proportion extend sort
- Quicksort
- Selection sort
- Heapsort
- Smoothsort
- Cartesian tree sort
- Tournament sort
- Cycle sort
- Weak-heap sort
- Insertion sort
- Shellsort
- Splaysort
- Tree sort
- Library sort
- Patience sorting
- Topological sorting
- Pre-topological order
- Pancake sorting
- Spaghetti sort