graph theory problem

This topic is 3346 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

You're given a directed graph. A node A in the graph is said to 'shadow' a node B if and only if the number of unique relevant paths from A to B, that do not have cycles and do not share any edges with each other, is greater than the number of such unique relevant paths from B to A. A path is considered relevant if and only if no node on the path is shadowed by the next node on the path. Find an algorithm to determine for any directed graph and for any given nodes A and B, whether A shadows B. I need this for a program I'm writing. I'm using the push-relabel maximum flow algorithm to compute the number of unique paths from A to B, but I need to make sure those paths are 'relevant', and since relevance is defined recursively by the shadow property which is defined in turn by relevance, I have an infinitely recursive definition which I can solve intuitively for small graphs but have been unable to devise an algorithm for that works in 100% of large graph cases. Any ideas?

Share on other sites
Are you sure the definitions even make sense? Would you mind walking me through how you determine if A shadows B in the graph with nodes {A, B, C} and edges {A->B, B->C, C->A}?

Share on other sites
Sure. Since B contains one relevant path to A, and A contains one relevant path to B, neither of them shadow each other. In checking path relevance recursively, I can use a stack of previously checked edges to ensure that there are no infinite recursions.

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5

• 11
• 16
• 26
• 10
• 11
• Forum Statistics

• Total Topics
633756
• Total Posts
3013707
×