Maximum Gain Round Trips with Cost Constraints

Details Maximum Gain Round Trips with Cost Constraints Maximum Gain Round Trips with Cost Constraints

2011-05-04

arxiv.org/abs/1105.0830v2

Computer Science

Social and Information Networks

Scientific paper

Searching for optimal ways in a network is an important task in multiple application areas such as social networks, co-citation graphs or road networks. In the majority of applications, each edge in a network is associated with a certain cost and an optimal way minimizes the cost while fulfilling a certain property, e.g connecting a start and a destination node. In this paper, we want to extend pure cost networks to so-called cost-gain networks. In this type of network, each edge is additionally associated with a certain gain. Thus, a way having a certain cost additionally provides a certain gain. In the following, we will discuss the problem of finding ways providing maximal gain while costing less than a certain budget. An application for this type of problem is the round trip problem of a traveler: Given a certain amount of time, which is the best round trip traversing the most scenic landscape or visiting the most important sights? In the following, we distinguish two cases of the problem. The first does not control any redundant edges and the second allows a more sophisticated handling of edges occurring more than once. To answer the maximum round trip queries on a given graph data set, we propose unidirectional and bidirectional search algorithms. Both types of algorithms are tested for the use case named above on real world spatial networks.

Affiliated with

Also associated with

No associations

Rating

Maximum Gain Round Trips with Cost Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximum Gain Round Trips with Cost Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum Gain Round Trips with Cost Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689537