Computer Science – Data Structures and Algorithms
Scientific paper
2011-12-06
Computer Science
Data Structures and Algorithms
32 pages, 7 figures
Scientific paper
We study the problem of determining strongly connected components (SCCs) of directed hypergraphs. The main contribution is an algorithm computing the terminal strongly connected components (ie SCCs which do not reach any other components than themselves). The time complexity of the algorithm is almost linear, which is a significant improvement over the known methods which are quadratic time. This also proves that the problems of testing strong connectivity, and determining the existence of a sink, can be both solved in almost linear time in directed hypergraphs. We also highlight an important discrepancy between the reachability relations in directed hypergraphs and graphs. We establish a superlinear lower bound on the size of the transitive reduction of the reachability relation in directed hypergraphs, showing that it is combinatorially more complex than in directed graphs. We also prove linear time reductions from combinatorial problems on the subset partial order, in particular from the well-studied problem of finding all minimal sets among a given family, to the problem of computing the SCCs in directed hypergraphs.
Allamigeon Xavier
No associations
LandOfFree
Strongly connected components of directed hypergraphs 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 Strongly connected components of directed hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strongly connected components of directed hypergraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-593932