← All proceedings

THE IIER INTERNATIONAL CONFERENCE

Proceedings cover: THE IIER INTERNATIONAL CONFERENCE

Jerusalem, Israel 20-10-2016

1 paper

  1. A Two-Step Algorithm For A Complex Problem of Shortest Paths on Weighted Graphs and 0-1 Knapsack

    Nadav Voloch

    Paper ID II-SIMISRL-20106-4684 · Pages 1-4

    Abstract

    two problems that are often studied and researches in computer science algorithms are the knapsack problem and the shortest paths on weighted graphs problem. Their combination is often addressed by dynamic programming solutions for the knapsack problem, using shortest path problem, with the creation of a knapsack graph. But these researches consider only two aspects of weight and value for an item/vertex, and here we address a different kind of problem in which we are taking into consideration three properties: item weight, item value and edge weight (that connects two items, but its weight is not depended on its vertices). The complex problem that combines these two, as a two-step problem on the same entities and a two-step algorithm for solving it, are the main ideas and subjects of this paper, in which this combination will be presented, along with several examples for it.

    Index terms- Knapsack problem, Shortest paths on weighted graphs, Dijkstra's algorithm, 0-1 knapsack problem, graph theory, dynamic programmingy.

    Download PDF