Premium
Heuristics for finding a maximum number of disjoint bounded paths
Author(s) -
Ronen D.,
Perl Y.
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140405
Subject(s) - bounded function , heuristics , combinatorics , disjoint sets , mathematics , vertex (graph theory) , heuristic , integer (computer science) , discrete mathematics , bounding overwatch , time complexity , mathematical optimization , computer science , graph , mathematical analysis , artificial intelligence , programming language
We consider the following problem: Given an integer k and a network G with two distinct vertices s and t , find a maximum number of vertex disjoint paths from s to t of length bounded by k . In a recent work [9] it was shown that for length greater than four this problem is NP ‐hard. In this paper we present a polynomial heuristic algorithm for the problem for general length. The algorithm is proved to give optimal solution for length less than five. Experiments show very good results for the algorithm.