**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**242

# Search results for: shortest paths.

##### 242 Fuzzy Shortest Paths Approximation for Solving the Fuzzy Steiner Tree Problem in Graphs

**Authors:**
Miloš Šeda

**Abstract:**

**Keywords:**
Steiner tree,
single shortest path problem,
fuzzyranking,
binary heap,
priority queue.

##### 241 All-Pairs Shortest-Paths Problem for Unweighted Graphs in O(n2 log n) Time

**Authors:**
Udaya Kumar Reddy K. R,
K. Viswanathan Iyer

**Abstract:**

Given a simple connected unweighted undirected graph G = (V (G), E(G)) with |V (G)| = n and |E(G)| = m, we present a new algorithm for the all-pairs shortest-path (APSP) problem. The running time of our algorithm is in O(n2 log n). This bound is an improvement over previous best known O(n2.376) time bound of Raimund Seidel (1995) for general graphs. The algorithm presented does not rely on fast matrix multiplication. Our algorithm with slight modifications, enables us to compute the APSP problem for unweighted directed graph in time O(n2 log n), improving a previous best known O(n2.575) time bound of Uri Zwick (2002).

**Keywords:**
Distance in graphs,
Dynamic programming,
Graphalgorithms,
Shortest paths.

##### 240 Improvement of the Shortest Path Problem with Geodesic-Like Method

**Authors:**
Wen-Haw Chen

**Abstract:**

**Keywords:**
shortest paths,
geodesic-like method,
NURBS surfaces.

##### 239 Evolutionary Algorithms for the Multiobjective Shortest Path Problem

**Authors:**
José Maria A. Pangilinan,
Gerrit K. Janssens

**Abstract:**

**Keywords:**
Multiobjective evolutionary optimization,
geneticalgorithms,
shortest paths.

##### 238 Binary Decision Diagrams: An Improved Variable Ordering using Graph Representation of Boolean Functions

**Authors:**
P.W. C. Prasad,
A. Assi,
A. Harb,
V.C. Prasad

**Abstract:**

This paper presents an improved variable ordering method to obtain the minimum number of nodes in Reduced Ordered Binary Decision Diagrams (ROBDD). The proposed method uses the graph topology to find the best variable ordering. Therefore the input Boolean function is converted to a unidirectional graph. Three levels of graph parameters are used to increase the probability of having a good variable ordering. The initial level uses the total number of nodes (NN) in all the paths, the total number of paths (NP) and the maximum number of nodes among all paths (MNNAP). The second and third levels use two extra parameters: The shortest path among two variables (SP) and the sum of shortest path from one variable to all the other variables (SSP). A permutation of the graph parameters is performed at each level for each variable order and the number of nodes is recorded. Experimental results are promising; the proposed method is found to be more effective in finding the variable ordering for the majority of benchmark circuits.

**Keywords:**
Binary decision diagrams,
graph representation,
Boolean functions representation,
variable ordering.

##### 237 Optimal and Critical Path Analysis of State Transportation Network Using Neo4J

**Authors:**
Pallavi Bhogaram,
Xiaolong Wu,
Min He,
Onyedikachi Okenwa

**Abstract:**

A transportation network is a realization of a spatial network, describing a structure which permits either vehicular movement or flow of some commodity. Examples include road networks, railways, air routes, pipelines, and many more. The transportation network plays a vital role in maintaining the vigor of the nation’s economy. Hence, ensuring the network stays resilient all the time, especially in the face of challenges such as heavy traffic loads and large scale natural disasters, is of utmost importance. In this paper, we used the Neo4j application to develop the graph. Neo4j is the world's leading open-source, NoSQL, a native graph database that implements an ACID-compliant transactional backend to applications. The Southern California network model is developed using the Neo4j application and obtained the most critical and optimal nodes and paths in the network using centrality algorithms. The edge betweenness centrality algorithm calculates the critical or optimal paths using Yen's *k*-shortest paths algorithm, and the node betweenness centrality algorithm calculates the amount of influence a node has over the network. The preliminary study results confirm that the Neo4j application can be a suitable tool to study the important nodes and the critical paths for the major congested metropolitan area.

**Keywords:**
Transportation network,
critical path,
connectivity reliability,
network model,
Neo4J application,
optimal path,
critical path,
edge betweenness centrality index,
node betweenness centrality index,
Yen’s k-shortest paths.

##### 236 Adding Edges between One Node and Every Other Node with the Same Depth in a Complete K-ary Tree

**Authors:**
Kiyoshi Sawada,
Takashi Mitsuishi

**Abstract:**

**Keywords:**
complete K-ary tree,
organization structure,
shortest path

##### 235 An Efficient and Optimized Multi Constrained Path Computation for Real Time Interactive Applications in Packet Switched Networks

**Authors:**
P.S. Prakash,
S. Selvan

**Abstract:**

Quality of Service (QoS) Routing aims to find path between source and destination satisfying the QoS requirements which efficiently using the network resources and underlying routing algorithm and to fmd low-cost paths that satisfy given QoS constraints. One of the key issues in providing end-to-end QoS guarantees in packet networks is determining feasible path that satisfies a number of QoS constraints. We present a Optimized Multi- Constrained Routing (OMCR) algorithm for the computation of constrained paths for QoS routing in computer networks. OMCR applies distance vector to construct a shortest path for each destination with reference to a given optimization metric, from which a set of feasible paths are derived at each node. OMCR is able to fmd feasible paths as well as optimize the utilization of network resources. OMCR operates with the hop-by-hop, connectionless routing model in IP Internet and does not create any loops while fmding the feasible paths. Nodes running OMCR not necessarily maintaining global view of network state such as topology, resource information and routing updates are sent only to neighboring nodes whereas its counterpart link-state routing method depend on complete network state for constrained path computation and that incurs excessive communication overhead.

**Keywords:**
QoS Routing,
Optimization,
feasible path,
multiple constraints.

##### 234 Integer Programming Model for the Network Design Problem with Facility Dependent Shortest Path Routing

**Authors:**
Taehan Lee

**Abstract:**

**Keywords:**
Integer programming,
multicommodity network
design,
routing,
shortest path.

##### 233 Approximation Algorithm for the Shortest Approximate Common Superstring Problem

**Authors:**
A.S. Rebaï,
M. Elloumi

**Abstract:**

**Keywords:**
Shortest approximate common superstring,
approximation algorithms,
strings overlaps,
complexities.

##### 232 Ant Colony Optimization for Feature Subset Selection

**Authors:**
Ahmed Al-Ani

**Abstract:**

**Keywords:**
Ant Colony Optimization,
ant systems,
feature
selection,
pattern recognition.

##### 231 Performance Comparison of Prim’s and Ant Colony Optimization Algorithm to Select Shortest Path in Case of Link Failure

**Authors:**
Rimmy Yadav,
Avtar Singh

**Abstract:**

**Keywords:**
Ant colony optimization,
link failure,
prim’s
algorithm.

##### 230 On a New Numerical Analysis for the Symmetric Shortest Queue Problem

**Authors:**
Tayeb Lardjane,
Rabah Messaci

**Abstract:**

We consider a network of two M/M/1 parallel queues having the same poisonnian arrival stream with rate λ. Upon his arrival to the system a customer heads to the shortest queue and stays until being served. If the two queues have the same length, an arriving customer chooses one of the two queues with the same probability. Each duration of service in the two queues is an exponential random variable with rate μ and no jockeying is permitted between the two queues. A new numerical method, based on linear programming and convex optimization, is performed for the computation of the steady state solution of the system.

**Keywords:**
Steady state solution,
matrix formulation,
convex set,
shortest queue,
linear programming.

##### 229 Skolem Sequences and Erdosian Labellings of m Paths with 2 and 3 Vertices

**Authors:**
H. V. Chen

**Abstract:**

**Keywords:**
c-Erdösian,
Skolem sequences,
magic labelling

##### 228 Optimal Path Planner for Autonomous Vehicles

**Authors:**
M. Imran Akram,
Ahmed Pasha,
Nabeel Iqbal

**Abstract:**

**Keywords:**
dynamic programming,
graph search,
path planning.

##### 227 Estimating Shortest Circuit Path Length Complexity

**Authors:**
Azam Beg,
P. W. Chandana Prasad,
S.M.N.A Senenayake

**Abstract:**

**Keywords:**
Monte Carlo circuit simulation data,
binary
decision diagrams,
neural network modeling,
shortest path length
estimation

##### 226 Urban Regeneration of Historic Paths: A Case Study of Kom El Dekka Historic Path

**Authors:**
Ahmed R. Ismail,
Hatem A. El Tawil,
Nevin G. Rezk

**Abstract:**

**Keywords:**
Community-oriented,
economic-based,
syntactical
analysis,
urban regeneration.

##### 225 Improving Survivability in Wireless Ad Hoc Network

**Authors:**
Seyed Ali Sadat Noori,
Elham Sahebi Bazaz

**Abstract:**

**Keywords:**
Wireless Ad Hoc Networks,
Reliability,
Routing,
Disjoint Path

##### 224 The Protection and Enhancement of the Roman Roads in Algeria

**Abstract:**

The Romain paths or roads offer a very interesting archaeological material, because they allow us to understand the history of human settlement and are also factors that increase territorial identity. Roman roads are one of the hallmarks of the Roman empire, which extends to North Africa. The objective of this investigation is to attract the attention of researchers of the importance of Roman roads and paths, which are found in Algeria, according to the quality of the materials and techniques used in this period our history, and to encourage other decision makers to protect and enhance these routes because the current urbanization, intensive agricultural practices, or simply forgotten, decreases the sustainability of this important historical heritage.

**Keywords:**
Romain paths,
material Materials,
Property,
Valuation.

##### 223 Geovisualization of Tourist Activity Travel Patterns Using 3D GIS: An Empirical Study of Tamsui, Taiwan

**Authors:**
Meng-Lung Lin,
Chien-Min Chu,
Chung-Hung Tsai,
Chih-Cheng Chen,
Chen-Yuan Chen

**Abstract:**

The study of tourist activities and the mapping of their routes in space and time has become an important issue in tourism management. Here we represent space-time paths for the tourism industry by visualizing individual tourist activities and the paths followed using a 3D Geographic Information System (GIS). Considerable attention has been devoted to the measurement of accessibility to shopping, eating, walking and other services at the tourist destination. I turns out that GIS is a useful tool for studying the spatial behaviors of tourists in the area. The value of GIS is especially advantageous for space-time potential path area measures, especially for the accurate visualization of possible paths through existing city road networks. This study seeks to apply space-time concepts with a detailed street network map obtained from Google Maps to measure tourist paths both spatially and temporally. These paths are further determined based on data obtained from map questionnaires regarding the trip activities of 40 individuals. The analysis of the data makes it possible to determining the locations of the more popular paths. The results can be visualized using 3D GIS to show the areas and potential activity opportunities accessible to tourists during their travel time.

**Keywords:**
Tourist activity analysis,
space-time path,
GIS,
geovisualization,
activity-travel pattern.

##### 222 Application of Activity-Based Costing Management System by Key Success Paths to Promote the Competitive Advantages and Operation Performance

**Authors:**
Mei-Fang Wu,
Shu-Li Wang,
Feng-Tsung Cheng

**Abstract:**

**Keywords:**
Activity-Based Costing,
Key success factors,
Key
success paths approach,
Key success paths,
Key failure paths.

##### 221 Feature Subset Selection Using Ant Colony Optimization

**Authors:**
Ahmed Al-Ani

**Abstract:**

**Keywords:**
Ant Colony Optimization,
ant systems,
feature
selection,
pattern recognition.

##### 220 Geospatial Network Analysis Using Particle Swarm Optimization

**Authors:**
Varun Singh,
Mainak Bandyopadhyay,
Maharana Pratap Singh

**Abstract:**

The shortest path (SP) problem concerns with finding the shortest path from a specific origin to a specified destination in a given network while minimizing the total cost associated with the path. This problem has widespread applications. Important applications of the SP problem include vehicle routing in transportation systems particularly in the field of in-vehicle Route Guidance System (RGS) and traffic assignment problem (in transportation planning). Well known applications of evolutionary methods like Genetic Algorithms (GA), Ant Colony Optimization, Particle Swarm Optimization (PSO) have come up to solve complex optimization problems to overcome the shortcomings of existing shortest path analysis methods. It has been reported by various researchers that PSO performs better than other evolutionary optimization algorithms in terms of success rate and solution quality. Further Geographic Information Systems (GIS) have emerged as key information systems for geospatial data analysis and visualization. This research paper is focused towards the application of PSO for solving the shortest path problem between multiple points of interest (POI) based on spatial data of Allahabad City and traffic speed data collected using GPS. Geovisualization of results of analysis is carried out in GIS.

**Keywords:**
GIS,
Outliers,
PSO,
Traffic Data.

##### 219 Influence of Slope Shape and Surface Roughness on the Moving Paths of a Single Rockfall

**Authors:**
Iau-Teh Wang,
Chin-Yu Lee

**Abstract:**

**Keywords:**
Rockfall,
Slope Shape,
Moving Path,
SurfaceRoughness.

##### 218 Learning Monte Carlo Data for Circuit Path Length

**Authors:**
Namal A. Senanayake,
A. Beg,
Withana C. Prasad

**Abstract:**

**Keywords:**
Monte Carlo data,
Binary decision diagrams,
Neural
network modeling,
Shortest path length estimation.

##### 217 Winding Numbers of Paths of Analytic Functions Zeros in Finite Quantum Systems

**Authors:**
Muna Tabuni

**Abstract:**

The paper contains an investigation of winding numbers of paths of zeros of analytic theta functions. We have considered briefly an analytic representation of finite quantum systems ZN. The analytic functions on a torus have exactly N zeros. The brief introduction to the zeros of analytic functions and there time evolution is given. We have discussed the periodic finite quantum systems. We have introduced the winding numbers in general. We consider the winding numbers of the zeros of analytic theta functions.

**Keywords:**
Winding numbers,
period,
paths of zeros.

##### 216 Increasing the Efficiency of Rake Receivers for Ultra-Wideband Applications

**Authors:**
Aimilia P. Doukeli,
Athanasios S. Lioumpas,
George K. Karagiannidis,
Panayiotis V. Frangos,
P. Takis Mathiopoulos

**Abstract:**

**Keywords:**
Adaptive Rake receivers,
diversity techniques,
fading channels,
UWB channel.

##### 215 Autonomous Virtual Agent Navigation in Virtual Environments

**Authors:**
Jafreezal Jaafar,
Eric McKenzie

**Abstract:**

**Keywords:**
Agent,
Navigation,
Demster Shafer,
Fuzzy Logic.

##### 214 Finding Viable Pollution Routes in an Urban Network under a Predefined Cost

**Authors:**
Dimitra Alexiou,
Stefanos Katsavounis,
Ria Kalfakakou

**Abstract:**

In an urban area the determination of transportation routes should be planned so as to minimize the provoked pollution taking into account the cost of such routes. In the sequel these routes are cited as pollution routes.

The transportation network is expressed by a weighted graph *G=(V,E,D,P)* where every vertex represents a location to be served and *E *contains unordered pairs (edges) of elements in *V* that indicate a simple road. The distances / cost and a weight that depict the provoked air pollution by a vehicle transition at every road are assigned to each road as well. These are the items of set *D* and* P *respectively.

Furthermore the investigated pollution routes must not exceed predefined corresponding values concerning the route cost and the route pollution level during the vehicle transition.

In this paper we present an algorithm that generates such routes in order that the decision maker selects the most appropriate one.

**Keywords:**
bi-criteria,
pollution,
shortest paths.

##### 213 Dempster-Shafer's Approach for Autonomous Virtual Agent Navigation in Virtual Environments

**Authors:**
Jafreezal Jaafar,
Eric McKenzie

**Abstract:**

This paper presents a solution for the behavioural animation of autonomous virtual agent navigation in virtual environments. We focus on using Dempster-Shafer-s Theory of Evidence in developing visual sensor for virtual agent. The role of the visual sensor is to capture the information about the virtual environment or identifie which part of an obstacle can be seen from the position of the virtual agent. This information is require for vitual agent to coordinate navigation in virtual environment. The virual agent uses fuzzy controller as a navigation system and Fuzzy α - level for the action selection method. The result clearly demonstrates the path produced is reasonably smooth even though there is some sharp turn and also still not diverted too far from the potential shortest path. This had indicated the benefit of our method, where more reliable and accurate paths produced during navigation task.

**Keywords:**
Agent,
navigation,
Dempster Shafer,
fuzzy logic.