Topological sort

From Glossary

Jump to: navigation, search

This sorts the nodes in a network such that each arc, say k-th, has LaTeX: \textstyle \mbox{Tail}(k) < \mbox{Head}(k) in the renumbered node indexes. This arises in a variety of combinatorial programs, such as those with precedence constraints. If the nodes cannot be topologically sorted, the network does not represent a partially ordered set. This means, for example, there is an inconsistency in the constraints, such as jobs that cannot be sequenced to satisfy the asserted precedence relations.

Personal tools