Algorithms for Junctions in Directed Acyclic Graphs

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

Given a pair of distinct vertices u, v in a graph G, we say that s is a junction of u, v if there are in G internally vertex disjoint directed paths from s to u and from s to v. We show how to characterize junctions in directed acyclic graphs. We also consider the two problems in the following and derive efficient algorithms to solve them. Given a directed acyclic graph G and a vertex s in G, how can we find all pairs of vertices of G such that s is a junction of them? And given a directed acyclic graph G and k pairs of vertices of G, how can we preprocess G such that all junctions of k given pairs of vertices could be listed quickly? All junctions of k pairs problem arises in an application in Anthropology and we apply our algorithm to find such junctions on kinship networks of some brazilian indian ethnic groups.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Algorithms for Junctions in Directed Acyclic Graphs 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 Algorithms for Junctions in Directed Acyclic Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Junctions in Directed Acyclic Graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-33173

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.