1 Answers
In graph theory, entanglement of a directed graph is a number measuring how stronglythe cycles of the graph are intertwined. It is defined in terms of a mathematical game in whichn cops try to capture a robber, who escapes along the edges of the graph. Similar to othergraph measures, such as cycle rank, some algorithmic problems, e.g. parity game, can beefficiently solved on graphs of bounded entanglement.
4 views
Answered