Give an algorithm for computing the diameter of a graph

Assignment Help Basic Computer Science
Reference no: EM131404953

The diameter of an unweighted graph is the maximum of all the shortest distances between pairs of vertices in the graph.

a. Give an algorithm for computing the diameter of a graph.

b. What is the Big Oh performance of your algorithm in terms of the number of vertices and edges in the graph?

c. Implement your algorithm.

d. Discuss possible ways that you can improve the performance of the algorithm.

Reference no: EM131404953

Questions Cloud

Draw a connected graph that contains these vertices : Suppose that five vertices are arranged at the corners of an imaginary pentagon. Draw a connected graph that contains these vertices.
Calculate the column percentage for freshman females : Calculate the row percentage for freshman females and explain what it means.- Calculate the column percentage for freshman females and explain what it means.
What is the problem-fallacy of equivocation : What is Metaphysics? List some Metaphysical questions, at least four.What is the problem/fallacy of equivocation?According to the reading, what are the three different meanings given to the term reality? Give examples of each one (Reality 1, Reality..
What are the rules of the american political system : What are the core ideals of the U.S. political system? How does the social contract reflect the ideals of the American political system? What are the "rules" of the American political system? What are the various views of political power?
Give an algorithm for computing the diameter of a graph : The diameter of an unweighted graph is the maximum of all the shortest distances between pairs of vertices in the graph.
Is given value a row percentage or a column percentage : Among those who have ever been divorced, what percentage smoked? Is this value a row percentage or a column percentage?
Discuss the affects of steroid use on athletic performance : Define ergogenic aid and explain how steroids are considered part of your definition. Discuss the affects of steroid use on athletic performance. Explain how steroids differ from the human growth hormone. Assess the medical risk of steroid use.Summar..
Write java statements that will construct directed graph : Discuss how a computer program might use this graph to play Nim.
Describe the concept of personal and political empowerment : Describe the concept of personal, interpersonal, and political empowerment. Explain an individual's involvement in multiple social systems-micro, mezzo, and macro-at work in the environment.

Reviews

Write a Review

Basic Computer Science Questions & Answers

  When users move the mouse

When users move the mouse over each thumb image of the item, an enlarged picture of the item will appear to the right of the thumb image. For each listed item, you should allow user to specify the numbers he/she intends to buy

  What is the relationship between d-amps and amps

Which type of orbit does a GEO satellite have? Explain your answer.

  Analyze the recent

U.S. > Analyze the recent (since Summer '14) decrease in the price of oil. How has supply and demand affected the price of oil today? Looking at the demand and supply determinants, what will most likely happen to the price by mid this year?

  Local community non-profit organization

Web site topic: Your boss has asked you to create a web site for: a local community non-profit organization that sells rummage sale items. This week, they have asked you to set up 1 page to show what the site will look like.

  What is the planning triangle

What is the planning triangle and what do the strategies lay out a map for?

  Using backups for complete recovery

Successful database recovery relies on the database being backed. This is what enables the database to recover data that were lost due to a media failure, loss of power, or any other type of disaster. Each time the online line redoes logs filled u..

  What the router does with a packet addressed

Suppose a router has built up the routing table shown in Table 4.14. The router can deliver packets directly over interfaces 0 and 1, or it can forward packets to routers R2, R3, or R4. Describe what the router does with a packet addressed to each..

  Which bacteria are more likely to erode

Notice that erosion only occurs on the surface of the biofilm. Discuss the impact of allowing ero-sion on the structure. Which bacteria are more likely to erode?

  Starting and naming a business

Shania Jackson is a mature Christian thinking of opening a Christian coffeehouse near Denver, Colorado. Her husband, Marvin, is open to making a contribution of capital to the business, but he has no interest in participating in its operation or m..

  Design a logic system for starting

The signal from the sensor operated by the guard is A, the signal from the operator is B, and the signal from workpiece is C. D is the signal from the remote sensor. (x represents don't care in truth table).

  Splice of string log containing the date

Assign to variable date the splice of string log containing the date (12/Feb ... -6000), using the indexing operator on string log. For each of the below string values of s, write the expression involving s and the string methods split() that eva..

  Program that reads a sequence of integers into an array

Write a program that reads a sequence of integers into an array and that computes the alternating sum of all elements in the array

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd