Thread Rating:
Upgrading Shortest Path Problem for Computer Network Routing
12122013, 07:36 PM




Upgrading Shortest Path Problem for Computer Network Routing
We introduce the Upgrading Shortest Paths Problem, a new
combinatorial problem for improving network connectivity with a wide range of applications from multicast communication to wildlife habitat conservation. We define the problem in terms of a network with node delays and a set of node upgrade actions, each associated with a cost and an upgraded (reduced) node delay. The goal is to choose a set of upgrade actions to minimize the shortest delay paths between demand pairs of terminals in the network, subject to a budget constraint. We show that this problem is NPhard. We describe and test two greedy algorithms against an exact algorithm on synthetic data and on a realworld instance from wildlife habitat conservation. While the greedy algorithms can do arbitrarily poorly in the worst case, they perform fairly well in practice. For most of the instances, taking the better of the two greedy solutions accomplishes within 5% of optimal on our benchmarks. Upgrading Shortest Path Routing.pdf (Size: 163.67 KB / Downloads: 14) 

« Next Oldest  Next Newest »



Possibly Related Threads...  
Thread:  Author  Replies:  Views:  Last Post  
Latest Seminar Computer Engineering Seminar 2014  Chandresh D Patel  0  1,351 
01312014 Last Post: Chandresh D Patel 

Latest Computer Engineering Seminar Topics  enggroom  1  1,779 
12242013 Last Post: TyroneMThomas 

Behavioral network engineering: making intrusion detection become autonomic  Ghanshyam  0  976 
12122013 Last Post: Ghanshyam 
User(s) browsing this thread:
1 Guest(s)
1 Guest(s)
Return to TopReturn to Content