MapReduce: Detecting Cycles in Network Graph by Ricky Ho.
From the post:
I recently received an email from an audience of my blog on Map/Reduce algorithm design regarding how to detect whether a graph is acyclic using Map/Reduce. I think this is an interesting problem and can imagine there can be wide range of application to it.
Although I haven’t solved this exact problem in the past, I’d like to sketch out my thoughts on a straightforward approach, which may not be highly optimized. My goal is to invite other audience who has solved this problem to share their tricks.
To define the problem: Given a simple directed graph, we want to tell whether it contains any cycles.
Relevant to processing of identifiers in topic maps which may occur on more than one topic (prior to merging).
What is your solution in a mapreduce context?
[…] Another Word For It Patrick Durusau on Topic Maps and Semantic Diversity « MapReduce: Detecting Cycles in Network Graph [Merging Duplicate Identifiers] […]
Pingback by Designing algorithms for Map Reduce « Another Word For It — January 8, 2013 @ 11:49 am