To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Entanglement (graph measure)

From Wikipedia, the free encyclopedia

In graph theory, entanglement of a directed graph is a number measuring how strongly the cycles of the graph are intertwined. It is defined in terms of a mathematical game in which n cops try to capture a robber, who escapes along the edges of the graph. Similar to other graph measures, such as cycle rank, some algorithmic problems, e.g. parity game, can be efficiently solved on graphs of bounded entanglement.

Definition

The entanglement game[1] is played by n cops against a robber on a directed graph G. Initially, all cops are outside the graph and the robber selects an arbitrary starting vertex v of G. Further on, the players move in turn. In each move the cops either stay where they are, or place one of them on the vertex currently occupied by the robber. The robber must move from her current vertex, along an edge, to a successor that is not occupied by a cop. The robber must move if no cop is following him. If there is no free successor to which the robber can move, she is caught, and the cops win. The robber wins if she cannot be caught, i.e. if the play can be made to last forever.

A graph G has entanglement n if n cops win in the entanglement game on G but n − 1 cops lose the game.

Properties and applications

Graphs of entanglement zero and one can be characterized as follows:[1]

  • entanglement of G is 0 if and only if G is acyclic
  • entanglement of G is 1 if and only if G is not acyclic, and in every strongly connected component of G there is a node whose removal makes the component acyclic.

Entanglement has also been a key notion in proving that the variable hierarchy of the modal mu calculus is strict.[2]

References

  1. ^ a b D. Berwanger and E. Grädel, Entanglement – A Measure for the Complexity of Directed Graphs with Applications to Logic and Games, Proceedings of LPAR'04, vol. 3452 of LNCS, pp. 209–223 (2004)
  2. ^ D. Berwanger, E. Grädel and G. Lenzi, The variable hierarchy of the mu-calculus is strict, Theory of Computing Systems, vol. 40, pp. 437–466 (2007)

External links

You can play the entanglement game online on tPlay.

This page was last edited on 9 August 2019, at 00:47
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.