What data structure is used to represent the tree t

Assignment Help Computer Engineering

Reference no: EM131984851

Problem

LetG=(V,E)bean(undirected)graphwithcostsce =0ontheedgese?E. Assume you are given a minimum-cost spanning tree T in G. Now assume that a new edge is added to G, connecting two nodes v, w ? V with cost c. (a) Give an efficient algorithm to test if T remains the minimum-cost spanning tree with the new edge added to G (but not to the tree T). Make your algorithm run in time O(|E|). Can you do it in O(|V|) time? Please note any assumptions you make about what data structure is used to represent the tree T and the graph G. (b) Suppose T is no longer the minimum-cost spanning tree. Give a linear-time algorithm (time O(|E|)) to update the tree T to the new minimum-cost spanning tree.

Reference no: EM131984851

Questions Cloud

Calculate the odds ratio of exposure to child abuse : 401076 Introduction to Epidemiology Assignment - Calculate the odds ratio of exposure to child abuse and risk of mental illness

What did you like most about taking linux : What did you like most about taking Linux? What are some of the pros and cons you experienced while learning Linux.

Exploring difference between application and system software : Lets begin class by exploring the differences between application software and system software. A Windows XP VM (Virtual Machine) running on Windows 7 machine.

What are the different page replacement algorithms : ITSA2003 - NETWORK OPERATING SYSTEM & CONFIGURATION - Expand the description to show the use of MAR and MBR

What data structure is used to represent the tree t : Can you do it in O(|V|) time? Please note any assumptions you make about what data structure is used to represent the tree T and the graph G.

What is the engineers duty to her employer : What is the engineer's duty to her employer? What is the engineer's duty to the environment and the public? Which duty is paramount?

Design an efficient algorithm to find post-office location : Design an efficient algorithm to find the post-office location minimizing the average distance between the villages and the post office.

Partner relationship to avoid bankruptcy : Also, I will address what led to there bankruptcy and how they could have created a partner relationship to avoid bankruptcy.

Prove that the distance of c is at least three : Let A be a matrix, and let C be the code consisting of all solution to Ax = 0. If A has neither a column of zeros. Prove that the distance of C is at least 3.

User Account

All Pages