Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Upgrading Shortest Path Problem for Computer Network Routing
12-12-2013, 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 NP-hard. We describe and test two greedy algorithms
against an exact algorithm on synthetic data and on a real-world 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.

.pdf  Upgrading Shortest Path Routing.pdf (Size: 163.67 KB / Downloads: 12)

 


Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Latest Seminar Computer Engineering Seminar 2014 Chandresh D Patel 0 1,290 01-31-2014
Last Post: Chandresh D Patel
Rainbow Latest Computer Engineering Seminar Topics enggroom 1 1,698 12-24-2013
Last Post: TyroneMThomas
  Behavioral network engineering: making intrusion detection become autonomic Ghanshyam 0 946 12-12-2013
Last Post: Ghanshyam

Forum Jump:


User(s) browsing this thread:
1 Guest(s)

Return to TopReturn to Content