Find a node i farthest from node k

Assignment Help Econometrics

Reference no: EM131259428

1. Let T be a depth-first search tree of a graph. Let D (i) denote an ordered set of descendants of the node i ∈ T, arranged in the same order in which the depth-first search method labeled them. Define last(i) as the last element in the set D (i). Modify the depthfirst search algorithm so that while computing the depth-first traversal of the network G, it also computes the last index of every node. Your algorithm should run in O(m) time.

2. Longest path-in a tree (Handler, 1973). A longest path in an undirected tree T is a path containing the maximum number of arcs. The longest path can start and end anywhere. Show that we can determine a longest path in T as follows: Select any node i and use a search algorithm to find a node k farthest from node i. Then use a search algorithm to find a node I farthest from node k. Show that the tree path from node k to node I is a longest path in T.

Reference no: EM131259428

Questions Cloud

Provide examples of unethical behavior : Give three examples of unethical behavior involving location selection and indicate which ethical principal is violated

Reference to herzberg two-factor theory : Explain how a manager motivates employees with reference to Herzberg's two-factor theory. I need a one and a half page paper on this question. Must be: Double spaced, 12 font, and standard essay format (introduction, middle, and conclusion paragr..

Describe an algorithm that decomposes any graph : For an acyclic network G with a specified source node s, outline an algorithm that enumerates all distinct directed paths from the source node to every other node in the network. The running time of your algorithm should be proportional to the tot..

Make a statement about the variability : You want to make a statement about the variability in the costs of personnel shelters - Given the information provided: Xbar = $47.25K, Summation of (Xi - Xbar)2 = 555.50

Find a node i farthest from node k : Then use a search algorithm to find a node I farthest from node k. Show that the tree path from node k to node I is a longest path in T.

Responsible for multiple suicides of its workers in china : Do you think Fox-conn should be responsible for multiple suicides of its workers in China? Given the relationship between Fox-conn and Apple. Do you think Apple should respond to it? How can such tragedy be prevented?

What is being said nonverbally by each person : What is being said nonverbally by each person? If he is waiting for a job interview, what impression do you think he is going to make? What is the interviewer (the woman on the right) communicating with her nonverbal positioning?

How would you formulate this investment problem : How would you formulate this investment problem as a shortest path problem, assuming that at any point in time, Mr. Jones invests all his funds in a single investment alternative.

Suitable for all kinds of jobs : Person-focused pay programs are not suitable for all kinds of jobs. Based on your understanding of person-focused pay concepts, identify at least three jobs for which this basis for pay is inappropriate. Be sure to provide your rationale, based up..

User Account

All Pages