 |
 |
***** To join INSNA, visit http://www.insna.org ***** On 3 Oct 2005, at 13:12, Ken Cousins wrote: > ***** To join INSNA, visit http://www.insna.org ***** > > I apologize for what I'm sure is a trivial question, but I'm > stumped. I > have a number of acyclical digraphs (representing hierarchies), which > often have multiple paths between the uppermost (originating) and > terminal nodes. > > I am comparing these graphs according to the longest path in each > (i.e., "slack" in the chain of command), but have not been able to > find > a metric that fits this exact problem. Since I'm sure this can't be > the > first time this question has come up, I turn to the SOCNET > community for > guidance. > > What is the correct terminology for such a metric? Just making sure we're on the same page: it sounds like what you're asking for is the term for the length of the longest path between any "source" of the digraph (corresponding to an individual with no supervisors) and any "sink" (an individual who does not supervise anyone). In the terminology of graph theory, the height of a tree (minimally connected acyclic digraph) is defined to be the maximum over all nodes' depths (path length between the root and the node). While a tree is a special case of an acyclic digraph, I'd say that the term "height" would be reasonably appropriate for acyclic digraphs in general as well (at least in the sense that people will probably understand what you mean if you use the term). Hope this helps-- Joshua jmadden@ics.uci.edu...Obscurium Per Obscurius...www.ics.uci.edu/~jmadden Joshua O'Madadhain: Information Scientist, Musician, and Philosopher- At-Tall It's that moment of dawning comprehension that I live for--Bill Watterson My opinions are too rational and insightful to be those of any organization. _____________________________________________________________________ SOCNET is a service of INSNA, the professional association for social network researchers (http://www.insna.org). To unsubscribe, send an email message to [log in to unmask] containing the line UNSUBSCRIBE SOCNET in the body of the message.