Sharif Digital Repository

We study a constrained version of the shortest path problem in simple polygons, in which the path must visit a given target polygon. We provide a worst-case optimal algorithm for this problem and also present a method to construct a subdivision of the simple polygon to efficiently answer queries to retrieve the shortest polygon-meeting paths from a single-source to the query point. The algorithms are linear, both in time and space, in terms of the complexity of the two polygons. © 2004 Elsevier B.V. All rights reserved  

In this paper, we consider acyclic networks of queues as a model to support the design of a dynamic production system. Each service station in the network represents a manufacturing or assembly operation. Only one type of product is produced by the system, but there exist several distinct production processes for manufacturing this product, each one corresponding with a directed path in the network of queues. In each network node, the number of servers in the corresponding service station is either one or infinity. The service time in each station is either exponentially distributed or belongs to a special class of Coxian distribution. Only in the source node, the service system may be... 

We are concerned with the design of a model and an algorithm for computing a shortest path in a network having various types of fuzzy arc lengths. First, we develop a new technique for the addition of various fuzzy numbers in a path using α -cuts by proposing a linear least squares model to obtain membership functions for the considered additions. Then, using a recently proposed distance function for comparison of fuzzy numbers. we propose a new approach to solve the fuzzy APSPP using of genetic algorithm. Examples are worked out to illustrate the applicability of the proposed model  

We are concerned with the design of a model and an algorithm for computing a shortest path in a network having various types of fuzzy arc lengths. First, we develop a new technique for the addition of various fuzzy numbers in a path using α-cuts. Then, we propose a regression model for obtaining membership function for the considered addition. Finally, we present a dynamic programming method for finding a shortest path in the network. An example is worked out to illustrate the applicability of the proposed approach  

In this paper, we study the problem of finding the shortest path in stochastic graphs and propose an iterative algorithm for solving it. This algorithm is based on distributed learning automata (DLA), and its objective is to use a DLA for finding the shortest path from the given source node to the given destination node whose weight is minimal in expected sense. At each stage of this algorithm, DLA specifies edges needed to be sampled. We show that the given algorithm finds the shortest path with minimum expected weight in stochastic graphs with high probability which can be close to unity as much as possible. We compare the given algorithm with some distributed learning automata-based... 

In this paper, we study the problem of finding the shortest path in stochastic graphs and propose an iterative algorithm for solving it. This algorithm is based on distributed learning automata (DLA), and its objective is to use a DLA for finding the shortest path from the given source node to the given destination node whose weight is minimal in expected sense. At each stage of this algorithm, DLA specifies edges needed to be sampled. We show that the given algorithm finds the shortest path with minimum expected weight in stochastic graphs with high probability which can be close to unity as much as possible. We compare the given algorithm with some distributed learning automata-based... 

In this paper we consider maintaining the visibility of a segment observer moving inside a simple polygon. A practical instance of this problem is to identify the regions of a planar scene illuminated by a fluorescent lamp while the lamp moves around. We consider both strong and weak visibility in this paper. Our method is based on the shortest path tree which builds a linear-sized data structure in O(n) time, where n is the number of the vertices of the underlying simple polygon P. We first compute VP(st̄), the initial view of the segment observer st̄. Then, as st̄ moves, each change of VP(st̄) can be computed in O(log2(|V P(st̄)|)) time when the observer is allowed to change its direction,... 

By applying shortest path analysis in stochastic networks, we introduce a new approach to obtain the reliability function of time-dependent systems. We assume that not all elements of the system are set to function from the beginning. Upon the failure of each element of the active path in the reliability graph, the system switches to the next path. Then, the corresponding elements are activated, and consequently, the connection between the input and the output is established. It is also assumed that each element exhibits a constant hazard rate and its lifetime is a random variable with exponential distribution. To evaluate the system reliability, we construct a directed stochastic network... 

We study a new class of visibility problems based on the notion of α-visibility. Given an angle α and a collection of line segments S in the plane, a segment t is said to be α-visible from a point p, if there exists an empty triangle with one vertex at p and the side opposite to p on t such that the angle at p is α. In this model of visibility, we study the classical variants of point visibility, weak and complete segment visibility, and the construction of the visibility graph. We also investigate the natural query versions of these problems, when α is either fixed or specified at query time  

This paper proposes a new approach to study the sensitivity analysis in the network flow problems, in particular, the minimum spanning tree and shortest path problems. In a sensitivity analysis, one looks for the amount of changes in the edges’ weights, number of edges or number of vertices such that the optimal solution, i.e., the minimum spanning tree or shortest path does not change. We introduce a novel approach, and develop associated equations and mathematics. We discuss two illustrative examples to show the applicability of the proposed approach. © International Journal of Industrial Engineering  

The problem of finding the expected shortest path in stochastic networks, where the presence of each node is probabilistic and the arc lengths are random variables, have numerous applications, especially in communication networks. The problem being NP-hard we use an ant colony system (ACS) to propose a metaheuristic algorithm for finding the expected shortest path. A new local heuristic is formulated for the proposed algorithm to consider the probabilistic nodes. The arc lengths are randomly generated based on the arc length distribution functions. Examples are worked out to illustrate the applicability of the proposed approach  

We are concerned with the design of a model and an algorithm for computing the shortest path in a network having various types of fuzzy arc lengths. First, a new technique is devised for the addition of various fuzzy numbers in a path using α-cuts by proposing a least squares model to obtain membership functions for the considered additions. Due to the complexity of the addition of various fuzzy numbers for larger problems, a genetic algorithm is presented for finding the shortest path in the network. For this, we apply a recently proposed distance function for comparison of fuzzy numbers. Examples are worked out to illustrate the applicability of the proposed approach  

We consider biobjective shortest path problems in networks with fuzzy arc lengths. Considering the available studies for single objective shortest path problems in fuzzy networks, using a distance function for comparison of fuzzy numbers, we propose three approaches for solving the biobjective problems. The first and second approaches are extensions of the labeling method to solve the single objective problem and the third approach is based on dynamic programming. The labeling methods usually producing several nondominated paths, we propose a fuzzy number ranking method to determine a fuzzy shortest path. Illustrative examples are worked out to show the effectiveness of our algorithms  

Let P be a set of n points in R3 amid a bounded number of obstacles. Consider the metric space M=(P,dM) where dM(p,q) is the geodesic distance of p and q, i.e., the length of a shortest path from p to q avoiding obstacles. When obstacles are axis-parallel boxes, we prove that M admits an 83-spanner with O(nlog3⁡n) edges. In other words, let S be a complete graph on n vertices where each node corresponds to a point p∈P. For nodes u and v of S corresponding to p,q∈P, the edge (u,v) is associated with the geodesic distance of p and q as its weight. We indeed prove that S admits a near linear-size t-spanner for some constant t. © 2020 Elsevier B.V  

Let P be a set of n points in R3 amid a bounded number of obstacles. Consider the metric space M=(P,dM) where dM(p,q) is the geodesic distance of p and q, i.e., the length of a shortest path from p to q avoiding obstacles. When obstacles are axis-parallel boxes, we prove that M admits an 83-spanner with O(nlog3⁡n) edges. In other words, let S be a complete graph on n vertices where each node corresponds to a point p∈P. For nodes u and v of S corresponding to p,q∈P, the edge (u,v) is associated with the geodesic distance of p and q as its weight. We indeed prove that S admits a near linear-size t-spanner for some constant t. © 2020 Elsevier B.V  

We study a constrained version of the shortest path problem in polygonal domains, in which the path must visit a given target polygon. We provide an efficient algorithm for this problem based on the wavefront propagation method and also present a method to construct a subdivision of the domain to efficiently answer queries to retrieve the constrained shortest paths from a single-source to the query point. © 2008 Springer-Verlag Berlin Heidelberg  

The shortest path problem is a classical and important network optimization problem appearing in many applications. We discuss the shortest path problem from a specified vertex to every other vertex on a network with imprecise arc lengths as fuzzy numbers. Using an order relation between fuzzy numbers, we propose a new algorithm to deal with the fuzzy shortest path problem. The algorithm is composed of a fuzzy shortest path length procedure and a similarity measure. The fuzzy shortest length method is proposed to find the fuzzy shortest length, and the fuzzy similarity measure is utilized to get the shortest path. Two illustrative examples are worked out to demonstrate the proposed algorithm...