Computer Science – Logic in Computer Science
Scientific paper
2007-05-03
FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, Inde (2007)
Computer Science
Logic in Computer Science
Scientific paper
10.1007/978-3-540-77050-3_42
Entanglement is a complexity measure of directed graphs that origins in fixed point theory. This measure has shown its use in designing efficient algorithms to verify logical properties of transition systems. We are interested in the problem of deciding whether a graph has entanglement at most k. As this measure is defined by means of games, game theoretic ideas naturally lead to design polynomial algorithms that, for fixed k, decide the problem. Known characterizations of directed graphs of entanglement at most 1 lead, for k = 1, to design even faster algorithms. In this paper we present an explicit characterization of undirected graphs of entanglement at most 2. With such a characterization at hand, we devise a linear time algorithm to decide whether an undirected graph has this property.
Belkhir Walid
Santocanale Luigi
No associations
LandOfFree
Undirected Graphs of Entanglement Two does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Undirected Graphs of Entanglement Two, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Undirected Graphs of Entanglement Two will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-496972