84 results on '"Shortest path problem"'
Search Results
2. Evaluation of Shortest path on multi stage graph problem using Dynamic approach under neutrosophic environment.
- Author
-
Raut, Prasanta Kumar, Behera, Siva Prasad, Broumi, Said, and Baral, Amarendra
- Subjects
- *
DYNAMIC programming , *COMPUTER engineering , *PROGRAMMING languages , *GRAPH theory , *ALGORITHMS - Abstract
The shortest path problem is a classic optimization problem in graph theory and computer technology. It involves identifying the shortest path between two nodes in a graph, where each edge has a numerical weight. In this paper, we put our effort into examining the use of the dynamic programming method to evaluate the shortest path (SP) between the two specified nodes in a multistage network where the parameter is a multi-value neutrosophic number (MVNN). Firstly, we propose an algorithm based on the forward and backward approach in an uncertain environment and also implement our approach in the Python-3 programming language. Furthermore, a numerical illustration has been provided to showcase the effectiveness and robustness of the novel model. [ABSTRACT FROM AUTHOR]
- Published
- 2024
3. Employing the Bellman-Ford Algorithm with Score Functions to Address the Linear Diophantine Fuzzy Shortest Path Problem in Network Analysis.
- Author
-
Kannan, Vidhya and Appasamy, Saraswathi
- Subjects
FUZZY numbers ,FUZZY graphs ,ALGORITHMS - Abstract
The realms of Intuitionistic Fuzzy Sets (IFSs), Pythagorean Fuzzy Sets (PFS), and qrung Orthopair Fuzzy Sets (q-ROFSs) have found extensive applications across various disciplines, notably in resolving real-world problems. However, limitations concerning membership and non-membership grades pose challenges to these theories. Efforts to mitigate these constraints have led to the introduction of a new concept, the Linear Diophantine Fuzzy Set (LDFS), with reference parameters. This study advances the shortest path (SP) problem for Linear Diophantine Fuzzy graphs. An innovative method for constructing direct network graphs within a Linear Diophantine Fuzzy (LDF) context is proposed. Distances or costs between nodes are encapsulated by Linear Diophantine Fuzzy numbers. The principal contribution of this investigation lies in proposing a novel approach to solving the Linear Fuzzy Diophantine Fuzzy shortest path problem using the Bellman-Ford algorithm for optimal solution attainment. Usage of the score function enables the comparison and identification of the minimum arc value between nodes. The proposed algorithm's validity is demonstrated through a numerical example, and a comparison with existing methodologies underscores the benefits of the proposed algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
4. Unifying Offline and Online Multi-Graph Matching via Finding Shortest Paths on Supergraph.
- Author
-
Jiang, Zetian, Wang, Tianzhe, and Yan, Junchi
- Subjects
- *
MULTIGRAPH , *ALGORITHMS , *SOURCE code , *DYNAMIC programming , *HEURISTIC algorithms , *ONLINE algorithms - Abstract
This paper addresses the problem of multiple graph matching (MGM) by considering both offline batch mode and online setting. We explore the concept of cycle-consistency over pairwise matchings and formulate the problem as finding optimal composition path on the supergraph, whose vertices refer to graphs and edge weights denote score function regarding consistency and affinity. By our theoretical study we show that the offline and online MGM on supergraph can be converted to finding all pairwise shortest paths and single-source shortest paths respectively. We adopt the Floyd algorithm and shortest path faster algorithm (SPFA) , to effectively find the optimal path. Extensive experimental results show our methods surpass state-of-the-art MGM methods, including CAO , MISM , IMGM , and many other recent methods in offline and online settings. Source code will be made publicly available. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
5. Optimization of Autonomous Agent Routes in Logistics Warehouse.
- Author
-
Markowski, Tomasz and Bilski, Piotr
- Subjects
- *
INTELLIGENT agents , *WAREHOUSES , *LOGISTICS , *ROBOTS , *ALGORITHMS - Abstract
The paper introduces the distributed framework for determining the shortest path of robots in the logistic applications, i.e. the warehouse with a swarm of robots cooperating in the Real-Time mode. The proposed solution uses the optimization routine to avoid the downtime and collisions between robots. The presented approach uses the reference model based on Dijkstra, Floyd-Warshall and Bellman-Ford algorithms, which search the path in the weighted undirected graph. Their application in the onboard robot's computer requires the analysis of the time efficiency. Results of comparative simulations for the implemented algorithms are presented. For their evaluation the data sets reflecting actual processes were used. Outcomes of experiments have shown that the tested algorithms are applicable for the logistic purposes, however their ability to operate in the Real-Time requires the detailed analysis. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
6. Real-Time Path Planning for Strategic Missions.
- Author
-
Vasconcelos, João Vítor R., Brandão, Alexandre S., and Sarcinelli-Filho, Mário
- Subjects
MOBILE robots ,SEARCH algorithms ,NATURAL disasters ,ALGORITHMS ,ROBOTS - Abstract
Featured Application: Our proposal has application in a real problem, whose objective is to guide a mobile robot to a target point in an environment that changes along time. These changes are characterized by the addition of obstacles that prevent navigation or the inability to follow a previously computed route, for instance scenarios of recent hazards or natural disasters. Robot navigation is still an open research topic, mainly regarding applications that require online planning. In this context, this manuscript presents an implementation of the Lifelong Planning A* (LPA*) search algorithm to guide a mobile robot in an environment that changes along time, by detecting obstacles and updating the current mapping information. Firstly, simulations validate the strategy, and later experiments confirm these results considering a real application. The result is that the LPA* algorithm is able to guide the mobile robot to its target in a changing environment. Obstacles are interactively included in the scene to force the route redesign and the seeking for a new optimal solution connecting the current robot position and its target position. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
7. ERA*: Enhanced Relaxed A* algorithm for solving the shortest path problem in regular grid maps.
- Author
-
Ammar, Adel
- Subjects
- *
GRIDS (Cartography) , *ALGORITHMS - Abstract
This paper introduces a novel algorithm for solving the point-to-point shortest path problem in a static regular 8-neighbor connectivity (G8) grid. This algorithm can be seen as a generalization of Hadlock algorithm to G8 grids, and is shown to be theoretically equivalent to the relaxed A ⁎ (R A ⁎) algorithm in terms of the provided solution's path length, but with substantial time and memory savings, due to a completely different computation strategy, based on defining a set of lookup matrices. Through an experimental study on grid maps of various types and sizes (1290 runs on 43 maps), it is proven to be 2.25 times faster than R A ⁎ and 17 times faster than the original A ⁎ , in average. Moreover, it is more memory-efficient, since it does not need to store a G score matrix. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
8. Shortest path problem using Bellman algorithm under neutrosophic environment.
- Author
-
Broumi, Said, Dey, Arindam, Talea, Mohamed, Bakali, Assia, Smarandache, Florentin, Nagarajan, Deivanayagampillai, Lathamaheswari, Malayalan, and Kumar, Ranjan
- Subjects
ALGORITHMS ,PROBLEM solving - Abstract
An elongation of the single-valued neutrosophic set is an interval-valued neutrosophic set. It has been demonstrated to deal indeterminacy in a decision-making problem. Real-world problems have some kind of uncertainty in nature and among them; one of the influential problems is solving the shortest path problem (SPP) in interconnections. In this contribution, we consider SPP through Bellman's algorithm for a network using interval-valued neutrosophic numbers (IVNNs). We proposed a novel algorithm to obtain the neutrosophic shortest path between each pair of nodes. Length of all the edges is accredited an IVNN. Moreover, for the validation of the proposed algorithm, a numerical example has been offered. Also, a comparative analysis has been done with the existing methods which exhibit the advantages of the new algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
9. Dijkstra algorithm for shortest path problem under interval-valued Pythagorean fuzzy environment.
- Author
-
Enayattabar, Mohammad, Ebrahimnejad, Ali, and Motameni, Homayun
- Subjects
FUZZY numbers ,ALGORITHMS ,FUZZY graphs ,FUZZY sets ,FUZZY mathematics - Abstract
Pythagorean fuzzy set as an extension of fuzzy set has been presented to handle the uncertainty in real-world decision-making problems. In this work, we formulate a shortest path (SP) problem in an interval-valued Pythagorean fuzzy environment. Here, the costs related to arcs are taken in the form of interval-valued Pythagorean fuzzy numbers (IVPFNs). The main contributions of this paper are fourfold: (1) the interval-valued Pythagorean fuzzy optimality conditions in directed networks are described to design of solution algorithm. (2) To do this, an improved score function is used to compare the costs between different paths with their arc costs represented by IVPFNs. (3) Based on these optimality conditions and the improved score function, the traditional Dijkstra algorithm is extended to find the cost of interval-valued Pythagorean fuzzy SP (IVPFSP) and corresponding IVPFSP. (4) Finally, a small sized telecommunication network is provided to illustrate the potential application of the proposed method. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
10. To Meet or Not to Meet: Finding the Shortest Paths in Road Networks.
- Author
-
Huang, Weihuang, Zhang, Yikai, Shang, Zechao, and Yu, Jeffrey Xu
- Subjects
- *
ROADS , *LOCATION-based services , *COMPUTER algorithms , *QUERYING (Computer science) , *COMPUTER networks - Abstract
Finding the shortest path in road networks becomes one of important issues in location based services (LBS). The problem of finding the optimal meeting point for a group of users has also been well studied in existing works. In this paper, we investigate a new problem for two users. Each user has his/her own source and destination. However, whether to meet before going to their destinations is with some uncertainty. We model it as minimum path pair ( MPP) query, which consists of two pairs of source and destination and a user-specified weight $\alpha$
to balance the two different needs. The result is a pair of paths connecting the two sources and destinations respectively, with minimal overall cost of the two paths and the shortest route between them. To solve MPP queries, we devise algorithms by enumerating node pairs. We adopt a location-based pruning strategy to reduce the number of node pairs for enumeration. An efficient algorithm based on point-to-point shortest path calculation is proposed to further improve query efficiency. We also give two fast approximate algorithms with approximation bounds. Extensive experiments are conducted to show the effectiveness and efficiency of our methods. [ABSTRACT FROM AUTHOR]- Published
- 2018
- Full Text
- View/download PDF
11. Dynamizing Dijkstra: A solution to dynamic shortest path problem through retroactive priority queue
- Author
-
Deepak Garg and Sunita
- Subjects
Sequence ,Dynamic shortest path ,General Computer Science ,Computer science ,Computation ,Retroactive data structure ,020206 networking & telecommunications ,02 engineering and technology ,Data structure ,lcsh:QA75.5-76.95 ,Set (abstract data type) ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,Topological graph theory ,020201 artificial intelligence & image processing ,lcsh:Electronic computers. Computer science ,Priority queue ,Dijkstra's algorithm ,Algorithm ,Algorithms - Abstract
Dynamic shortest path algorithms are the ones which are used to accommodate the online sequence of update operations to the underlying graph topology and also facilitate the subsequent query operations. Many solutions exist for the different versions of the problem, all of which identify the set of vertices whose shortest paths may be affected by the changes and then update their shortest paths according to the update sequence. In this paper, we are dynamizing the Dijkstra algorithm which helps to efficiently solve the dynamic single source shortest path problem. Dynamization is achieved by using the retroactive priority queue data structure. Retroactive data structure identify the set of affected vertices step by step and thus help to accommodate the changes in least number of computations. So, with a suitable dynamic graph representation and the use of retroactive priority queue, we have proposed algorithm to dynamize Dijkstra algorithm giving solution of dynamic single source shortest path problem with complexity O(nlg m) for the update time. We have performed experimental analysis by comparing the performance of the proposed algorithm with other algorithms. Our experimental results indicate that the proposed algorithm has better performance in terms of time and memory usage.
- Published
- 2021
12. Graph-based information diffusion method for prioritizing functionally related genes in protein-protein interaction networks
- Author
-
Minh Pham and Olivier Lichtarge
- Subjects
business.industry ,Computer science ,Graph based ,Gene function annotation ,Computational Biology ,Computational biology ,Protein protein interaction network ,Article ,Text mining ,Phenotype ,Network diffusion ,Large networks ,Shortest path problem ,Graph (abstract data type) ,Humans ,Protein Interaction Maps ,business ,Gene ,Biological network ,Network validation ,Algorithms - Abstract
Shortest path length methods are routinely used to validate whether genes of interest are functionally related to each other based on biological network information. However, the methods are computationally intensive, impeding extensive utilization of network information. In addition, non-weighted shortest path length approach, which is more frequently used, often treat all network connections equally without taking into account of confidence levels of the associations. On the other hand, graph-based information diffusion method, which employs both the presence and confidence weights of network edges, can efficiently explore large networks and has previously detected meaningful biological patterns. Therefore, in this study, we hypothesized that the graph-based information diffusion method could prioritize genes with relevant functions more efficiently and accurately than the shortest path length approaches. We demonstrated that the graph-based information diffusion method substantially differentiated not only genes participating in same biological pathways (p << 0.0001) but also genes associated with specific human drug-induced clinical symptoms (p << 0.0001) from random. Furthermore, the diffusion method prioritized these functionally related genes faster and more accurately than the shortest path length approaches (pathways: p = 2.7e-28, clinical symptoms: p = 0.032). These data show the graph-based information diffusion method can be routinely used for robust prioritization of functionally related genes, facilitating efficient network validation and hypothesis generation, especially for human phenotype-specific genes.
- Published
- 2020
13. Herding Packets: How to Route Packets on the Best Path Through a Network with Multiple Criteria
- Author
-
Samson, Judith Theresa
- Subjects
Computer engineering ,Algorithms ,Computer Networking ,Internet ,Routing ,Semirings ,Shortest Path Problem - Abstract
Algorithms for finding the shortest path between two nodes in a graph have been heavily studied for decades. Half a century ago solutions were found for the specific class of problems that involves finding the path of least length, when edges are weighted with a single metric. For example, although the Bellman-Ford and Dijkstra algorithms use different methodologies, both techniques depend on a single metric where the lengths of paths are found by adding path weights in the conventional way. The situation becomes more complicated when multiple metrics or single metrics other than simple Euclidean distance are involved. In these cases, the definition of ``shortest,'' or ``best'' is not straightforward. In addition, it is not always a simple matter to verify that packets in a distributed network are forwarded on best paths that are guaranteed loop-free. We call the set of edge weights, plus the rules that determine how paths are concatenated and compared, the path algebra. We find that the structure of a path algebra is the key to understanding how packets will be forwarded in a distributed network; specifically whether they will be forwarded on best, loop-free paths. This is independent of any path-finding algorithm. We show that ``best'' paths and loop-free paths are separate (albeit subtly related) properties, that are dependent on whether or not a path algebra is monotonic and strictly bounded. We examine examples of path algebras that possess various combinations of those two properties in order to illustrate how they affect the construction of forwarding paths. Finally, we prove that if a path algebra is monotonic and strictly bounded, it is guaranteed to produce forwarding paths that are best and loop-free. Previous works have introduced these ideas in separate contexts. We provide a consistent framework and prove general concepts that have only been introduced or discussed in special cases.
- Published
- 2016
14. Better tired than lost: Turtle ant trail networks favor coherence over short edges
- Author
-
James A. R. Marshall, Saket Navlakha, Arjun Chandrasekhar, Cortnea Austin, and Deborah M. Gordon
- Subjects
0106 biological sciences ,Arboreal locomotion ,Forage (honey bee) ,Information Theory ,Social Sciences ,Cephalotes ,Walking ,Trail pheromone ,01 natural sciences ,ComputingMethodologies_ARTIFICIALINTELLIGENCE ,Biochemistry ,Pheromones ,law.invention ,Trees ,Mathematical and Statistical Techniques ,law ,Psychology ,Biology (General) ,Turtle (robot) ,0303 health sciences ,Ecology ,biology ,Animal Behavior ,Behavior, Animal ,Mathematical Models ,Eukaryota ,Plants ,Turtles ,Insects ,Computational Theory and Mathematics ,Modeling and Simulation ,Animal Sociality ,Vertebrates ,Physical Sciences ,Enhanced Data Rates for GSM Evolution ,Network Analysis ,Algorithms ,Computer network ,Research Article ,Computer and Information Sciences ,Arthropoda ,QH301-705.5 ,Research and Analysis Methods ,010603 evolutionary biology ,Models, Biological ,03 medical and health sciences ,Cellular and Molecular Neuroscience ,Genetics ,Animals ,Molecular Biology ,Ecology, Evolution, Behavior and Systematics ,030304 developmental biology ,Behavior ,business.industry ,Ants ,Node (networking) ,Organisms ,Biology and Life Sciences ,Reptiles ,Computational Biology ,Graph theory ,Feeding Behavior ,15. Life on land ,biology.organism_classification ,Hymenoptera ,Invertebrates ,Testudines ,Graph Theory ,Shortest path problem ,Amniotes ,Routing (electronic design automation) ,business ,Zoology ,Entomology ,Mathematics - Abstract
Creating a routing backbone is a fundamental problem in both biology and engineering. The routing backbone of the trail networks of arboreal turtle ants (Cephalotes goniodontus) connects many nests and food sources using trail pheromone deposited by ants as they walk. Unlike species that forage on the ground, the trail networks of arboreal ants are constrained by the vegetation. We examined what objectives the trail networks meet by comparing the observed ant trail networks with networks of random, hypothetical trail networks in the same surrounding vegetation and with trails optimized for four objectives: minimizing path length, minimizing average edge length, minimizing number of nodes, and minimizing opportunities to get lost. The ants’ trails minimized path length by minimizing the number of nodes traversed rather than choosing short edges. In addition, the ants’ trails reduced the opportunity for ants to get lost at each node, favoring nodes with 3D configurations most likely to be reinforced by pheromone. Thus, rather than finding the shortest edges, turtle ant trail networks take advantage of natural variation in the environment to favor coherence, keeping the ants together on the trails., Author summary We investigated the trail networks of arboreal turtle ants in the canopy of the tropical forest, to ask what characterizes the colony’s choice of foraging paths within the vegetation. We monitored day to day changes in the junctions and edges of trail networks of colonies in the dry forest of western Mexico. We compared the paths used by the ants to simulated random paths in the surrounding vegetation. We found that the paths of turtle ants prioritize coherence, keeping ants together on the trail, over minimizing the average edge length. The choice of paths reduces the number of junctions in the trail where ants could get lost, and favors junctions with a physical configuration that makes it likely that successive ants will reinforce the same path. Our work suggests that design principles that emphasize keeping information flow constrained to streamlined, coherent trails may be useful in human-designed distributed routing and transport networks or robot swarms.
- Published
- 2021
15. A Unified Approach to Spatial Proximity Query Processing in Dynamic Spatial Networks
- Author
-
Hyung-Ju Cho
- Subjects
Databases, Factual ,Exploit ,Range query (data structures) ,Computer science ,spatial proximity query ,02 engineering and technology ,TP1-1185 ,computer.software_genre ,Biochemistry ,Article ,Analytical Chemistry ,k-nearest neighbors algorithm ,dynamic spatial network ,020204 information systems ,Server ,0202 electrical engineering, electronic engineering, information engineering ,Electrical and Electronic Engineering ,Instrumentation ,Chemical technology ,Process (computing) ,InformationSystems_DATABASEMANAGEMENT ,020206 networking & telecommunications ,Atomic and Molecular Physics, and Optics ,Range (mathematics) ,unified batch algorithm ,Shortest path problem ,Scalability ,nearest neighbor query ,Data mining ,computer ,Algorithms ,range query - Abstract
Nearest neighbor (NN) and range (RN) queries are basic query types in spatial databases. In this study, we refer to collections of NN and RN queries as spatial proximity (SP) queries. At peak times, location-based services (LBS) need to quickly process SP queries that arrive simultaneously. Timely processing can be achieved by increasing the number of LBS servers, however, this also increases service costs. Existing solutions evaluate SP queries sequentially, thus, such solutions involve unnecessary distance calculations. This study proposes a unified batch algorithm (UBA) that can effectively process SP queries in dynamic spatial networks. With the proposed UBA, the distance between two points is indicated by the travel time on the shortest path connecting them. The shortest travel time changes frequently depending on traffic conditions. The goal of the proposed UBA is to avoid unnecessary distance calculations for nearby SP queries. Thus, the UBA clusters nearby SP queries and exploits shared distance calculations for query clusters. Extensive evaluations using real-world roadmaps demonstrated the superiority and scalability of UBA compared with state-of-the-art sequential solutions.
- Published
- 2021
- Full Text
- View/download PDF
16. A column generation-based algorithm for solving combined inventory and routing problems.
- Author
-
Franco-Franco, Carlos and Figueroa-García, Juan Carlos
- Subjects
- *
COLUMN generation (Algorithms) , *VEHICLE routing problem , *INVENTORY control , *ALGORITHMS , *PROBLEM solving , *PRICING , *LINEAR programming - Abstract
This paper presents a column generation algorithm for solving combined vehicle and inventory problems. This problem is based on the idea of coordinating customer inventory levels through a minimum routing cost. This is a combinatory decision problem since vehicle routing and inventory problems, are combined. Using the column generation method, we can iteratively generate interesting routes to the system, based on their dual costs, this is routes that will improve the quality of the objective function because its reduced costs are negatives. The initial mixed integer problem has to be relaxed for getting its reduced costs. The sub problem is defined as the shortest path problem that returns a set of desirable routes. Finally, when the set of desirable routes is obtained, the mixed integer model should select a set of routes that fulfill both minimum shipping costs and the constraints of the system. [ABSTRACT FROM AUTHOR]
- Published
- 2016
17. Path planning for the Platonic solids on prescribed grids by edge-rolling
- Author
-
Ngoc Tam Lam, Ian Howard, and Lei Cui
- Subjects
Models, Molecular ,Computer science ,Twins ,Molecular Conformation ,Geometry ,Astronomical Sciences ,02 engineering and technology ,Trees ,0303 health sciences ,Multidisciplinary ,Crystallography ,Applied Mathematics ,Simulation and Modeling ,Physics ,Planetary Sciences ,Eukaryota ,Robotics ,Plants ,021001 nanoscience & nanotechnology ,Condensed Matter Physics ,Physical Sciences ,symbols ,Tetrahedron ,Crystal Structure ,Medicine ,Engineering and Technology ,Solar System ,Cube ,0210 nano-technology ,Robots ,Algorithms ,Research Article ,Science ,Research and Analysis Methods ,Platonic solid ,03 medical and health sciences ,Dodecahedron ,symbols.namesake ,Position (vector) ,Mathematics::Metric Geometry ,Solid State Physics ,Computer Simulation ,030304 developmental biology ,Mechanical Engineering ,Organisms ,Biology and Life Sciences ,Orientation (vector space) ,Dihedral Angles ,Shortest path problem ,Mathematics ,Penrose tiling ,Developmental Biology - Abstract
The five Platonic solids—tetrahedron, cube, octahedron, dodecahedron, and icosahedron—have found many applications in mathematics, science, and art. Path planning for the Platonic solids had been suggested, but not validated, except for solving the rolling-cube puzzles for a cubic dice. We developed a path-planning algorithm based on the breadth-first-search algorithm that generates a shortest path for each Platonic solid to reach a desired pose, including position and orientation, from an initial one on prescribed grids by edge-rolling. While it is straightforward to generate triangular and square grids, various methods exist for regular-pentagon tiling. We chose the Penrose tiling because it has five-fold symmetry. We discovered that a tetrahedron could achieve only one orientation for a particular position.
- Published
- 2021
18. An Approach for the Fast Calculation Method of Pareto Solutions of a Two-objective Network.
- Author
-
Takahashi, Natsumi, Akiba, Tomoaki, Nomura, Shuhei, and Yamamoto, Hisashi
- Subjects
PROBLEM solving ,MATHEMATICAL optimization ,WIRELESS sensor nodes ,ALGORITHMS ,PARETO analysis - Abstract
The shortest path problem is a kind of optimization problem and its aim is to find the shortest path connecting two specific nodes in a network, where each edge has its distance. When considering not only the distances between the nodes but also some other information, the problem is formulated as a multi-objective shortest path problem that involves multiple conflicting objective functions. The multi-objective shortest path problem is a kind of optimization problem of multi-objective network. In the general cases, multi-objectives are rarely optimized by a solution. So, to solve the multi-objective shortest path problem leads to obtaining Pareto solutions. An algorithm for this problem has been proposed by using the extended Dijkstra's algorithm. However, this algorithm for obtaining Pareto solutions has many useless searches for paths. In this study, we consider two-objective shortest path problem and propose efficient algorithms for obtaining the Pareto solutions. Our proposed algorithm can reduce more search space than existing algorithms, by solving a single-objective shortest path problem. The results of the numerical experiments suggest that our proposed algorithms reduce the computing time and the memory size for obtaining the Pareto solutions. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
19. Computing nearest neighbour interchange distances between ranked phylogenetic trees
- Author
-
Lena Collienne and Alex Gavryushkin
- Subjects
0106 biological sciences ,FOS: Computer and information sciences ,68W40, 68Q25, 03D15 ,Computational complexity theory ,Computer science ,Inference ,Computational Complexity (cs.CC) ,92B05 ,010603 evolutionary biology ,01 natural sciences ,Article ,Combinatorics ,03 medical and health sciences ,Quadratic equation ,Computer Science - Data Structures and Algorithms ,Rank (graph theory) ,Cluster Analysis ,Data Structures and Algorithms (cs.DS) ,Phylogeny ,030304 developmental biology ,0303 health sciences ,Phylogenetic tree ,Models, Genetic ,Applied Mathematics ,68Q25 ,Computational Biology ,Agricultural and Biological Sciences (miscellaneous) ,Tree (data structure) ,Computer Science - Computational Complexity ,Modeling and Simulation ,Tree rearrangement ,Shortest path problem ,F.2.0 ,Algorithms - Abstract
Many popular algorithms for searching the space of leaf-labelled (phylogenetic) trees are based on tree rearrangement operations. Under any such operation, the problem is reduced to searching a graph where vertices are trees and (undirected) edges are given by pairs of trees connected by one rearrangement operation (sometimes called a move). Most popular are the classical nearest neighbour interchange, subtree prune and regraft, and tree bisection and reconnection moves. The problem of computing distances, however, is $${\mathbf {N}}{\mathbf {P}}$$ N P -hard in each of these graphs, making tree inference and comparison algorithms challenging to design in practice. Although ranked phylogenetic trees are one of the central objects of interest in applications such as cancer research, immunology, and epidemiology, the computational complexity of the shortest path problem for these trees remained unsolved for decades. In this paper, we settle this problem for the ranked nearest neighbour interchange operation by establishing that the complexity depends on the weight difference between the two types of tree rearrangements (rank moves and edge moves), and varies from quadratic, which is the lowest possible complexity for this problem, to $${\mathbf {N}}{\mathbf {P}}$$ N P -hard, which is the highest. In particular, our result provides the first example of a phylogenetic tree rearrangement operation for which shortest paths, and hence the distance, can be computed efficiently. Specifically, our algorithm scales to trees with tens of thousands of leaves (and likely hundreds of thousands if implemented efficiently).
- Published
- 2020
20. A Model for Range Estimation and Energy-Efficient Routing of Electric Vehicles in Real-World Conditions
- Author
-
Cedric De Cauwer, Thierry Coosemans, Wouter Verbeke, Joeri Van Mierlo, Electromobility research centre, and Electrical Engineering and Power Electronics
- Subjects
Mathematical optimization ,Technology ,Engineering, Civil ,Electric vehicles ,Computer science ,Transportation ,Internal resistance ,Data modeling ,Predictive models ,Engineering ,Approximation error ,0502 economics and business ,BATTERY ,Driving range ,Routing ,050210 logistics & transportation ,Cost allocation ,Science & Technology ,HEALTH ESTIMATION ,Mechanical Engineering ,05 social sciences ,Transportation Science & Technology ,ALGORITHMS ,Data models ,Engineering, Electrical & Electronic ,Energy consumption ,STATE ,Computer Science Applications ,Roads ,Automotive Engineering ,Shortest path problem ,Graph (abstract data type) ,energy-efficient routing ,Estimation - Abstract
This paper presents an integrated model for energy consumption and range estimation, capable of energy-efficient routing. This integrated model predicts the energy consumption on all road segments in the road network and applies shortest path algorithms to calculate energy-efficient routes. A temperature-dependent model of the battery internal resistance based on real-world data translates the energy consumption prediction into driving range. The graph representation of the road network is transformed from a node-based graph to an edge-based graph to allow cost allocation of one edge based on the characteristics of the preceding edge. The integrated model is used to perform an analysis of energy-efficient routes for a real-life scenario. The analysis showed that the energy-optimal route is different from the time- and distance-optimal route with energy-efficiency gains up to 37% for the chosen scenario. The energy-efficient route tends to lean toward a distance-optimal route in the case of low auxiliary consumption and to lean toward a time-optimal route in the case of high auxiliary consumption. The energy-efficient route generation is tested in real life for one case of the chosen scenario. The measured results showed a good match with the predicted values for the energy consumption with a 9% mean relative error and preserved the ranking of all routes in terms of the travel distance, travel time, and energy consumption. The proposed integrated model is a functional model for energy consumption in real-life that differentiates many energy consumption influencing factors and produces energy-efficient routes with good accuracy.
- Published
- 2020
21. Multi-start heuristic approaches for one-to-one pickup and delivery problems with shortest-path transport along real-life paths
- Author
-
Jian Xiong, Weixiong Zha, Zhuo Fu, and Xin Qi
- Subjects
Optimization ,Computer and Information Sciences ,Mathematical optimization ,Structural Engineering ,Computer science ,Heuristic (computer science) ,Science ,0211 other engineering and technologies ,Transportation ,02 engineering and technology ,Research and Analysis Methods ,Infographics ,Mathematical and Statistical Techniques ,Random Searching ,Residence Characteristics ,0502 economics and business ,Heuristics ,Simulated Annealing ,Evolutionary Biology ,Evolutionary Theory ,050210 logistics & transportation ,021103 operations research ,Multidisciplinary ,Mathematical Models ,Heuristic ,Data Visualization ,Applied Mathematics ,Simulation and Modeling ,05 social sciences ,Biology and Life Sciences ,Models, Theoretical ,Solver ,Built Structures ,Variable (computer science) ,Physical Sciences ,Path (graph theory) ,Simulated annealing ,Shortest path problem ,Engineering and Technology ,Feasibility Studies ,Medicine ,Graphs ,Automobiles ,Mathematics ,Algorithms ,Research Article - Abstract
The One-to-one Pickup and Delivery Problem with Shortest-path Transport along Real-life Paths (OPDPSTRP) is presented in this paper. It is a variation of the One-to-one Pickup and Delivery Problem (OPDP), which is common in daily life, such as the Passenger Train Operation Plans (PTOP) and partial Taxi-sharing Problem. Unlike the classical OPDP, in the OPDPSTRP, (1) each demand must be transported along the shortest path according to passengers/shippers requirements, and (2) each vehicle should travel along a real-life path. First, six route structure rules are proposed for the OPDPSTRP, and a kind of Mixed-Integer Programming (MIP) models is formulated for it. Second, A Variable Neighborhood Descent (VND), a Variable Neighborhood Research (VNS), a Multi-Start VND (MS_VND) and a Multi-Start VNS (MS_VNS) with five neighborhood operators has been developed to solve the problem. Finally, The Gurobi solver, the VND, the VNS, the MS_VND and the MS_VNS have been compared with each other by 84 random instances partitioned in small size connected graphs, medium size connected graphs and large size connected graphs. From the test results we found that solutions generated by these approaches are often comparable with those found by the Gurobi solver, and the solutions found by these approaches are better than the solutions found by the Gurobi solver when solving instances with larger numbers of demands. In almost all instances, the MS_VND significantly outperforms the VND and the VNS in terms of solution quality, and outperforms the MS_VNS both in terms of solution quality and CPU time. In the instances with large numbers of demands, the MS_VND is still able to generate good feasible solutions in a reasonable CPU time, which is of vital practical significance for real-life instances.
- Published
- 2020
22. An Algorithm for Managing Aircraft Movement on an Airport Surface.
- Author
-
Tancredi, Urbano, Accardo, Domenico, Fasano, Giancarmine, Renga, Alfredo, Rufino, Giancarlo, and Maresca, Giuseppe
- Subjects
- *
AIR traffic control , *ALGORITHMS , *INBOUND travel , *OUTBOUND travel , *MATHEMATICAL models - Abstract
The present paper focuses on the development of an algorithm for safely and optimally managing the routing of aircraft on an airport surface in future airport operations. This tool is intended to support air traffic controllers' decision-making in selecting the paths of all aircraft and the engine startup approval time for departing ones. Optimal routes are sought for minimizing the time both arriving and departing aircraft spend on an airport surface with engines on, with benefits in terms of safety, efficiency and costs. The proposed algorithm first computes a standalone, shortest path solution from runway to apron or vice versa, depending on the aircraft being inbound or outbound, respectively. For taking into account the constraints due to other traffic on an airport surface, this solution is amended by a conflict detection and resolution task that attempts to reduce and possibly nullify the number of conflicts generated in the first phase. An example application on a simple Italian airport exemplifies how the algorithm can be applied to true-world applications. Emphasis is given on how to model an airport surface as a weighted and directed graph with non-negative weights, as required for the input to the algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
23. Shortest path problem in rectangular complexes of global nonpositive curvature
- Author
-
Chepoi, Victor and Maftuleac, Daniela
- Subjects
- *
METRIC spaces , *EUCLIDEAN geometry , *GENERALIZATION , *HYPERBOLIC spaces , *ALGORITHMS , *BIPARTITE graphs - Abstract
Abstract: metric spaces constitute a far-reaching common generalization of Euclidean and hyperbolic spaces and simple polygons: any two points x and y of a metric space are connected by a unique shortest path . In this paper, we present an efficient algorithm for answering two-point distance queries in rectangular complexes and two of theirs subclasses, ramified rectilinear polygons ( rectangular complexes in which the links of all vertices are bipartite graphs) and squaregraphs ( rectangular complexes arising from plane quadrangulations in which all inner vertices have degrees ⩾4). Namely, we show that for a rectangular complex with n vertices, one can construct a data structure of size so that, given any two points , the shortest path between x and y can be computed in time, where p and q are vertices of two faces of containing the points x and y, respectively, such that and is the distance between p and q in the underlying graph of . If is a ramified rectilinear polygon, then one can construct a data structure of optimal size and answer two-point shortest path queries in time, where Δ is the maximal degree of a vertex of . Finally, if is a squaregraph, then one can construct a data structure of size and answer two-point shortest path queries in time. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
24. SHORTEST PATH SIMPLEX ALGORITHM WITH A MULTIPLE PIVOT RULE:: A COMPARATIVE STUDY.
- Author
-
SEDEÑO-NODA, A. and GONZÁLEZ-MARTÍN, C.
- Subjects
ALGORITHMS ,PATHS & cycles in graph theory ,SIMPLEXES (Mathematics) ,SET theory ,COMPARATIVE studies ,EXPERIMENTS ,BASES (Linear topological spaces) - Abstract
This paper introduces a new multiple pivot shortest path simplex method by choosing a subset of non-basic arcs to simultaneously enter into the basis. It is shown that the proposed shortest path simplex method requires O(n) multiple pivots and its running time is O(nm). Results from a computational study comparing the proposed method from previously known methods are reported. The experimental show that the proposed rule is more efficient than the considered shortest path simplex pivot rules. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
25. An ant colony optimization algorithm for the bi-objective shortest path problem.
- Author
-
Ghoseiri, Keivan and Nadjari, Behnam
- Subjects
ALGORITHMS ,COMBINATORIAL optimization ,MATHEMATICAL optimization ,PROJECT management ,PERFORMANCE evaluation ,MULTIPLE criteria decision making ,PARETO analysis - Abstract
Abstract: Multi-objective shortest path problem (MOSP) is an extension of a traditional single objective shortest path problem that seeks for the efficient paths satisfying several conflicting objectives between two nodes of a network. MOSP is one of the most important problems in network optimization with wide applications in telecommunication industries, transportation and project management. This research presents an algorithm based on multi-objective ant colony optimization (ACO) to solve the bi-objective shortest path problem. To analyze the efficiency of the algorithm and check for the quality of solutions, experimental analyses are conducted. Two sets of small and large sized problems that generated randomly are solved. Results on the set problems are compared with those of label correcting solutions that is the most known efficient algorithm for solving MOSP. To compare the Pareto optimal frontiers produced by the suggested ACO algorithm and the label correcting algorithm, some performance measures are employed that consider and compare the distance, uniformity distribution and extension of the Pareto frontiers. The results on the set of instance problems show that the suggested algorithm produces good quality non-dominated solutions and time saving in computation of large-scale bi-objective shortest path problems. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
26. A faster algorithm for the single source shortest path problem with few distinct positive lengths.
- Author
-
Orlin, James B., Madduri, Kamesh, Subramani, K., and Williamson, M.
- Subjects
ALGORITHMS ,PATHS & cycles in graph theory ,GRAPH theory ,COMBINATORICS ,MATHEMATICAL analysis - Abstract
Abstract: In this paper, we propose an efficient method for implementing Dijkstra''s algorithm for the Single Source Shortest Path Problem (SSSPP) in a graph whose edges have positive length, and where there are few distinct edge lengths. The SSSPP is one of the most widely studied problems in theoretical computer science and operations research. On a graph with n vertices, m edges and K distinct edge lengths, our algorithm runs in time if , and time, otherwise. We tested our algorithm against some of the fastest algorithms for SSSPP on graphs with arbitrary but positive lengths. Our experiments on graphs with few edge lengths confirmed our theoretical results, as the proposed algorithm consistently dominated the other SSSPP algorithms, which did not exploit the special structure of having few distinct edge lengths. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
27. Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks.
- Author
-
Gutiérrez, Eliécer and Medaglia, Andrés L.
- Subjects
- *
ROADS , *COMBINATORIAL optimization , *COMBINATORICS , *MATHEMATICAL optimization , *GEOGRAPHIC information systems , *ALGORITHMS - Abstract
In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogotá’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
28. ML Symbol Detection Based on the Shortest Path Algorithm for MIMO Systems.
- Author
-
Kyungchun Lee and Joohwan Chun
- Subjects
- *
MAXIMUM likelihood statistics , *ALGORITHMS , *COMPUTER input-output equipment , *COMPUTATIONAL complexity , *ITERATIVE methods (Mathematics) , *MATRICES (Mathematics) , *COMPUTER systems , *COMPUTER network architectures , *ELECTRONIC data processing - Abstract
This paper presents a new maximum likelihood (ML) symbol detection algorithm for multiple-input multiple-output (MIMO) systems. To achieve the ML performance with low complexity, we search the integer points corresponding to symbol vectors in increasing order of the distance from the unconstrained least-squares solution. For each integer point, we test if it is the ML solution, and continue the integer point search until one of searched points is determined to be the ML solution. We present an efficient iterative search strategy, which is based on the shortest path algorithm for a graph. The simulation results show that the proposed algorithm has the lower complexity compared to the sphere decoding for channel matrices having low condition numbers. For further complexity reduction, we propose to use scaling, lattice-reduction, and regularization techniques. By applying these techniques, the computational complexity of proposed algorithm is reduced significantly when the channel matrix has a high condition number. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
29. The On-Line Shortest Path Problem Under Partial Monitoring.
- Author
-
György, András, Linder, Tamás, Lugosi, Gábor, and Ottucsák, György
- Subjects
- *
ONLINE education , *ALGORITHMS , *ROUTING (Computer network management) , *COMPUTER assisted instruction , *COMPUTER network management - Abstract
The on-line shortest path problem is considered under various models of partial monitoring. Given a weighted directed acyclic graph whose edge weights can change in an arbitrary (adversarial) way, a decision maker has to choose in each round of a game a path between two distinguished vertices such that the loss of the chosen path (defined as the sum of the weights of its composing edges) be as small as possible. In a setting generalizing the multi-armed bandit problem, after choosing a path, the decision maker learns only the weights of those edges that belong to the chosen path. For this problem, an algorithm is given whose average cumulative loss in n rounds exceeds that of the best path, matched off-line to the entire sequence of the edge weights, by a quantity that is proportional to 1/√n and depends only polynomially on the number of edges of the graph. The algorithm can be implemented with complexity that is linear in the number of rounds n (i.e., the average complexity per round is constant) and in the number of edges. An extension to the so-called label efficient setting is also given, in which the decision maker is informed about the weights of the edges corresponding to the chosen path at a total of m « n time instances. Another extension is shown where the decision maker competes against a time-varying path, a generalization of the problem of tracking the best expert. A version of the multi-armed bandit setting for shortest path is also discussed where the decision maker learns only the total weight of the chosen path but not the weights of the individual edges on the path. Applications to routing in packet switched networks along with simulation results are also presented. [ABSTRACT FROM AUTHOR]
- Published
- 2007
30. UTILIZING DISTRIBUTED LEARNING AUTOMATA TO SOLVE STOCHASTIC SHORTEST PATH PROBLEMS.
- Author
-
Beigy, Hamid and Meybodi, M. R.
- Subjects
- *
PROBABILISTIC automata , *ALGORITHMS , *STOCHASTIC analysis , *SIMULATION methods & models , *SYSTEM analysis - Abstract
In this paper, we first introduce a network of learning automata, which we call it as distributed learning automata and then propose some iterative algorithms for solving stochastic shortest path problem. These algorithms use distributed learning automata to find a policy that determines a path from a source node to a destination node with minimal expected cost (length). In these algorithms, at each stage distributed learning automata determines which edges to be sampled. This sampling method may result in decreasing unnecessary samples and hence decreasing the running time of algorithms. It is shown that the shortest path is found with a probability as close as to unity by proper choice of the parameters of the proposed algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
31. A self-stabilizing algorithm for the shortest path problem assuming the distributed demon
- Author
-
Huang, Tetz C.
- Subjects
- *
ALGORITHMS , *TRANSPORTATION , *COMMUNICATION , *SELF-stabilization (Computer science) , *COMPUTER algorithms - Abstract
Abstract: Shortest path finding has a variety of applications in transportation and communication.In this paper, we study a well-known self-stabilizing algorithm for the shortest path problem for the distributed systems. The previous works on this topic had two assumptions that can be relaxed in this paper. First, in the previous works, the systems were assumed to be integral-weighted, whereas in this paper, the systems are real-weighted. Second, and more importantly, the previous works have shown that the algorithm is self-stabilizing under the more restricted central demon model, whereas in this paper, we give a rigorous proof showing that the algorithm is actually self-stabilizing under the more general distributed demon model. The work in this paper is of significance because in the existing literature on self-stabilizing systems, most of the papers regarding the distributed demon are for the ring networks only; there are very few papers that discuss the self-stabilizing algorithms for the general distributed systems assuming the distributed demon model. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
32. Optimal testing policies for diagnosing patients with intermediary probability of disease
- Author
-
Edilson F. Arruda, Basilio de Bragança Pereira, Clarissa Antunes Thiers, and Bernardo Rangel Tura
- Subjects
Warrant ,Test strategy ,Stochastic Processes ,0303 health sciences ,Mathematical optimization ,A priori probability ,Series (mathematics) ,Optimality criterion ,Computer science ,Posterior probability ,Medicine (miscellaneous) ,Bayes Theorem ,03 medical and health sciences ,0302 clinical medicine ,Artificial Intelligence ,Diagnosis ,Shortest path problem ,Humans ,Algorithms ,030217 neurology & neurosurgery ,Probability ,030304 developmental biology ,Sequence (medicine) - Abstract
This paper proposes a stochastic shortest path approach to find an optimal sequence of tests to confirm or discard a disease, for any prescribed optimality criterion. The idea is to select the best sequence in which to apply a series of available tests, with a view at reaching a diagnosis with minimum expenditure of resources. The proposed approach derives an optimal policy whereby the decision maker is provided with a test strategy for each a priori probability of disease, aiming to reach posterior probabilities that warrant either immediate treatment or a not-ill diagnosis.
- Published
- 2019
33. Particle swarm optimization-based collision avoidance
- Author
-
Timur Inan, Ahmet Fevzi Baba, and Inan T., BABA A. F.
- Subjects
Decision support system ,Computer science ,Sinyal İşleme ,Mühendislik ,ENGINEERING ,02 engineering and technology ,Information Systems, Communication and Control Engineering ,Bilgisayarla Görme ve Örüntü Tanıma ,Yapay Zeka ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science (miscellaneous) ,Collision avoidance ,Bilgisayar Bilimi Uygulamaları ,ENGINEERING, ELECTRICAL & ELECTRONIC ,Artificial neural network ,Computer Sciences ,Elektrik ve Elektronik Mühendisliği ,Particle swarm optimization ,General Engineering ,Computer Science Applications ,Bilgisayar Bilimi (çeşitli) ,Physical Sciences ,NAVIGATION ,Engineering and Technology ,Bilgisayar Bilimi ,Computer Vision and Pattern Recognition ,Bilgi Sistemleri, Haberleşme ve Kontrol Mühendisliği ,COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE ,General Computer Science ,neural network ,Real-time computing ,Human error ,Mühendislik (çeşitli) ,algorithms ,Fuzzy logic ,BİLGİSAYAR BİLİMİ, YAPAY ZEKA ,Genel Mühendislik ,Artificial Intelligence ,Bilgisayar Bilimleri ,collision avoidance ,Electrical and Electronic Engineering ,Engineering, Computing & Technology (ENG) ,Genel Bilgisayar Bilimi ,Engineering (miscellaneous) ,Particle swarm optimization,collision avoidance,collision risk assessment,neural network,fuzzy ,fuzzy ,020206 networking & telecommunications ,Mühendislik, Bilişim ve Teknoloji (ENG) ,COMPUTER SCIENCE ,Collision ,collision risk assessment ,Fizik Bilimleri ,Shortest path problem ,Signal Processing ,MÜHENDİSLİK, ELEKTRİK VE ELEKTRONİK ,Mühendislik ve Teknoloji ,Algoritmalar - Abstract
Collision risk assessment and collision avoidance of vessels have always been an important topic in ocean engineering. Decision support systems are increasingly becoming the focus of many studies in the maritime industry today as vessel accidents are often caused by human error. This study proposes an anticollision decision support system that can determine surrounding obstacles by using the information received from radar systems, obtain the position and speed of obstacles within a certain time period, and suggest possible routes to prevent collisions. In this study we use a neural network to predict the subsequent positions of surrounding vessels, a fuzzy logic system to obtain the risk of collision, and a particle swarm optimization algorithm to find the safe and shortest path for collision avoidance.
- Published
- 2019
34. Applying the Dijkstra Algorithm to Solve a Linear Diophantine Fuzzy Environment.
- Author
-
Parimala, Mani, Jafari, Saeid, Riaz, Muhamad, and Aslam, Muhammad
- Subjects
- *
FUZZY numbers , *ALGORITHMS , *DIRECTED graphs , *FUZZY sets , *TELECOMMUNICATION systems , *FUZZY graphs - Abstract
Linear Diophantine fuzzy set (LDFS) theory expands Intuitionistic fuzzy set (IFS) and Pythagorean fuzzy set (PyFS) theories, widening the space of vague and uncertain information via reference parameters owing to its magnificent feature of a broad depiction area for permissible doublets. We codify the shortest path (SP) problem for linear Diophantine fuzzy graphs. Linear Diophantine fuzzy numbers (LDFNs) are used to represent the weights associated with arcs. The main goal of the presented work is to create a solution technique for directed network graphs by introducing linear Diophantine fuzzy (LDF) optimality constraints. The weights of distinct routes are calculated using an improved score function (SF) with the arc values represented by LDFNs. The conventional Dijkstra method is further modified to find the arc weights of the linear Diophantine fuzzy shortest path (LDFSP) and coterminal LDFSP based on these enhanced score functions and optimality requirements. A comparative analysis was carried out with the current approaches demonstrating the benefits of the new algorithm. Finally, to validate the possible use of the proposed technique, a small-sized telecommunication network is presented. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
35. Influence of time-series normalization, number of nodes, connectivity and graph measure selection on seizure-onset zone localization from intracranial EEG
- Author
-
Willeke Staljanssens, Ana Coito, Octavian V. Lie, Serge Vulliemoz, and Pieter van Mierlo
- Subjects
Male ,Multivariate statistics ,Computer science ,Electroencephalography/methods ,02 engineering and technology ,Seizure onset zone ,Signal-To-Noise Ratio ,0302 clinical medicine ,Theoretical ,Models ,Number of connectivity nodes ,EPILEPTOGENIC NETWORKS ,Radiological and Ultrasound Technology ,Functional connectivity ,Brain ,Seizures/physiopathology ,Electroencephalography ,Electrodes, Implanted ,Causality ,Neurology ,Area Under Curve ,Granger causality ,Female ,Anatomy ,Algorithms ,Normalization (statistics) ,Adult ,FUNCTIONAL BRAIN CONNECTIVITY ,Technology and Engineering ,0206 medical engineering ,Electrocorticography/methods ,03 medical and health sciences ,Seizures ,Humans ,Radiology, Nuclear Medicine and imaging ,Ictal ,Computer Simulation ,Time-series normalization ,Electrodes ,Original Paper ,Epilepsy ,Intracranial EEG ,Brain/physiopathology ,business.industry ,Pattern recognition ,Graph theory ,Models, Theoretical ,020601 biomedical engineering ,Intracranial eeg ,ddc:616.8 ,Multivariate directed functional connectivity ,Shortest path problem ,PATTERNS ,Neurology (clinical) ,Artificial intelligence ,Implanted ,Electrocorticography ,business ,030217 neurology & neurosurgery - Abstract
We investigated the influence of processing steps in the estimation of multivariate directed functional connectivity during seizures recorded with intracranial EEG (iEEG) on seizure-onset zone (SOZ) localization. We studied the effect of (i) the number of nodes, (ii) time-series normalization, (iii) the choice of multivariate time-varying connectivity measure: Adaptive Directed Transfer Function (ADTF) or Adaptive Partial Directed Coherence (APDC) and (iv) graph theory measure: outdegree or shortest path length. First, simulations were performed to quantify the influence of the various processing steps on the accuracy to localize the SOZ. Afterwards, the SOZ was estimated from a 113-electrodes iEEG seizure recording and compared with the resection that rendered the patient seizure-free. The simulations revealed that ADTF is preferred over APDC to localize the SOZ from ictal iEEG recordings. Normalizing the time series before analysis resulted in an increase of 25–35% of correctly localized SOZ, while adding more nodes to the connectivity analysis led to a moderate decrease of 10%, when comparing 128 with 32 input nodes. The real-seizure connectivity estimates localized the SOZ inside the resection area using the ADTF coupled to outdegree or shortest path length. Our study showed that normalizing the time-series is an important pre-processing step, while adding nodes to the analysis did only marginally affect the SOZ localization. The study shows that directed multivariate Granger-based connectivity analysis is feasible with many input nodes (> 100) and that normalization of the time-series before connectivity analysis is preferred. Electronic supplementary material The online version of this article (10.1007/s10548-018-0646-7) contains supplementary material, which is available to authorized users.
- Published
- 2018
36. Charting the algorithmic complexity of waypoint routing
- Author
-
Stefan Schmid, Klaus-Tycho Foerster, Saeed Akhoondian Amiri, and Riko Jacob
- Subjects
Computer Networks and Communications ,business.industry ,Computer science ,ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,Complexity ,Waypoints ,01 natural sciences ,Waypoint ,Algorithmic complexity ,010201 computation theory & mathematics ,VNFs ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,Graph (abstract data type) ,business ,Dijkstra's algorithm ,Software ,Algorithms ,Computer network - Abstract
Modern computer networks support interesting new routing models in which traffic flows from a source sto a destination t can be flexibly steered through a sequence of waypoints, such as (hardware) middleboxes or (virtualized) network functions (VNFs), to create innovative network services like service chains or segment routing. While the benefits and technological challenges of providing such routing models have been articulated and studied intensively over the last years, less is known about the underlying algorithmic traffic routing problems. The goal of this paper is to provide the network community with an overview of algorithmic techniques for waypoint routing and also inform about limitations due to computational hardness. In particular, we put the waypoint routing problem into perspective with respect to classic graph theoretical problems. For example, we find that while computing a shortest path from a source s to a destination t is simple (e.g., using Dijkstra's algorithm), the problem of finding a shortest route from s to t via a single waypoint already features a deep combinatorial structure.
- Published
- 2018
37. Cell transmission model of dynamic assignment for urban rail transit networks
- Author
-
Guangming Xu, Feng Shi, Shuo Zhao, and Feilian Zhang
- Subjects
Urban rail transit ,Computer science ,0211 other engineering and technologies ,lcsh:Medicine ,Social Sciences ,Transportation ,02 engineering and technology ,Urban Environments ,Cognition ,Beijing ,Psychology ,Cell Cycle and Cell Division ,lcsh:Science ,Cell Transmission Model ,Queueing theory ,021103 operations research ,Multidisciplinary ,Applied Mathematics ,Simulation and Modeling ,05 social sciences ,Transportation Infrastructure ,Terrestrial Environments ,Cell Processes ,Physical Sciences ,Engineering and Technology ,Assignment problem ,Algorithms ,Network Analysis ,Research Article ,Schedule ,Mathematical optimization ,Computer and Information Sciences ,Decision Making ,Research and Analysis Methods ,Civil Engineering ,0502 economics and business ,Railroads ,050210 logistics & transportation ,lcsh:R ,Ecology and Environmental Sciences ,Urbanization ,Cognitive Psychology ,Biology and Life Sciences ,Cell Biology ,Models, Theoretical ,Computing Methods ,Roads ,Transmission (telecommunications) ,Shortest path problem ,Resource allocation ,Cognitive Science ,lcsh:Q ,Mathematics ,Neuroscience - Abstract
For urban rail transit network, the space-time flow distribution can play an important role in evaluating and optimizing the space-time resource allocation. For obtaining the space-time flow distribution without the restriction of schedules, a dynamic assignment problem is proposed based on the concept of continuous transmission. To solve the dynamic assignment problem, the cell transmission model is built for urban rail transit networks. The priority principle, queuing process, capacity constraints and congestion effects are considered in the cell transmission mechanism. Then an efficient method is designed to solve the shortest path for an urban rail network, which decreases the computing cost for solving the cell transmission model. The instantaneous dynamic user optimal state can be reached with the method of successive average. Many evaluation indexes of passenger flow can be generated, to provide effective support for the optimization of train schedules and the capacity evaluation for urban rail transit network. Finally, the model and its potential application are demonstrated via two numerical experiments using a small-scale network and the Beijing Metro network.
- Published
- 2017
38. Xwalk: computing and visualizing distances in cross-linking experiments
- Author
-
Lars Malmström, Ruedi Aebersold, and Abdullah Kahraman
- Subjects
Statistics and Probability ,Web server ,Theoretical computer science ,Computer science ,Peptide ,computer.software_genre ,Biochemistry ,Mass Spectrometry ,Accessible surface area ,03 medical and health sciences ,Protein structure ,Amino Acid Sequence ,Amino Acids ,Molecular Biology ,Peptide sequence ,Topology (chemistry) ,030304 developmental biology ,chemistry.chemical_classification ,Internet ,0303 health sciences ,030302 biochemistry & molecular biology ,Computational Biology ,Proteins ,Substrate (chemistry) ,Structural Bioinformatics ,Protein Structure, Tertiary ,Computer Science Applications ,Amino acid ,Applications Note ,Computational Mathematics ,Computational Theory and Mathematics ,chemistry ,Shortest path problem ,Path (graph theory) ,Programming Languages ,Biological system ,computer ,Algorithms ,Software - Abstract
Bioinformatics, 27 (15), ISSN:1367-4803, ISSN:1460-2059
- Published
- 2017
39. Shortest Path Solution of Trapezoidal Fuzzy Neutrosophic Graph Based on Circle-Breaking Algorithm.
- Author
-
Yang, Lehua, Li, Dongmei, and Tan, Ruipu
- Subjects
- *
ALGORITHMS , *FUZZY graphs , *FUZZY numbers - Abstract
The shortest path problem is a topic of increasing interest in various scientific fields. The damage to roads and bridges caused by disasters makes traffic routes that can be accurately expressed become indeterminate. A neutrosophic set is a collection of the truth membership, indeterminacy membership, and falsity membership of the constituent elements. It has a symmetric form and indeterminacy membership is their axis of symmetry. In uncertain environments, the neutrosophic number can more effectively express the edge distance. The objectives in this study are to solve the shortest path problem of the neutrosophic graph with an edge distance expressed using trapezoidal fuzzy neutrosophic numbers (TrFNN) and resolve the edge distance according to the score and exact functions based on the TrFNN. Accordingly, the use of a circle-breaking algorithm is proposed to solve the shortest path problem and estimate the shortest distance. The feasibility of this method is verified based on two examples, and the rationality and effectiveness of the approach are evaluated by comparing it with the Dijkstra and Bellman algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
40. Optimization for Service Routes of Pallet Service Center Based on the Pallet Pool Mode
- Author
-
Rui Song, Kang Zhou, and Shiwei He
- Subjects
Mathematical optimization ,Time Factors ,General Computer Science ,Article Subject ,Computer science ,General Mathematics ,0211 other engineering and technologies ,02 engineering and technology ,lcsh:Computer applications to medicine. Medical informatics ,lcsh:RC321-571 ,Vehicle routing problem ,Stochastic simulation ,0202 electrical engineering, electronic engineering, information engineering ,Humans ,Computer Simulation ,Pallet ,lcsh:Neurosciences. Biological psychiatry. Neuropsychiatry ,Simulation ,Service (business) ,Stochastic Processes ,021103 operations research ,Artificial neural network ,General Neuroscience ,General Medicine ,Models, Theoretical ,Route inspection problem ,Shortest path problem ,Programming paradigm ,lcsh:R858-859.7 ,020201 artificial intelligence & image processing ,Neural Networks, Computer ,Algorithms ,Research Article - Abstract
Service routes optimization (SRO) of pallet service center should meet customers’ demand firstly and then, through the reasonable method of lines organization, realize the shortest path of vehicle driving. The routes optimization of pallet service center is similar to the distribution problems of vehicle routing problem (VRP) and Chinese postman problem (CPP), but it has its own characteristics. Based on the relevant research results, the conditions of determining the number of vehicles, the one way of the route, the constraints of loading, and time windows are fully considered, and a chance constrained programming model with stochastic constraints is constructed taking the shortest path of all vehicles for a delivering (recycling) operation as an objective. For the characteristics of the model, a hybrid intelligent algorithm including stochastic simulation, neural network, and immune clonal algorithm is designed to solve the model. Finally, the validity and rationality of the optimization model and algorithm are verified by the case.
- Published
- 2016
- Full Text
- View/download PDF
41. Estimation of Distributed Fermat-Point Location for Wireless Sensor Networking
- Author
-
Yanuarius Teofilus Larosa, Jiann-Liang Chen, Tsui-Lien Chiang, and Po-Hsian Huang
- Subjects
Computer science ,Distributed computing ,Minimum bounding box algorithms ,lcsh:Chemical technology ,Biochemistry ,Article ,Analytical Chemistry ,Computer Communication Networks ,wireless sensor network ,Minimum bounding box ,Node (computer science) ,Humans ,distributed fermat-point location estimation (DF-PLE) ,Fermat point ,Computer Simulation ,lcsh:TP1-1185 ,Electrical and Electronic Engineering ,Instrumentation ,Signal Processing, Computer-Assisted ,Wireless sensor networking ,Atomic and Molecular Physics, and Optics ,Key distribution in wireless sensor networks ,Shortest path problem ,Geographic Information Systems ,bounding box algorithm ,Wireless sensor network ,Algorithm ,Wireless Technology ,Algorithms - Abstract
This work presents a localization scheme for use in wireless sensor networks (WSNs) that is based on a proposed connectivity-based RF localization strategy called the distributed Fermat-point location estimation algorithm (DFPLE). DFPLE applies triangle area of location estimation formed by intersections of three neighboring beacon nodes. The Fermat point is determined as the shortest path from three vertices of the triangle. The area of estimated location then refined using Fermat point to achieve minimum error in estimating sensor nodes location. DFPLE solves problems of large errors and poor performance encountered by localization schemes that are based on a bounding box algorithm. Performance analysis of a 200-node development environment reveals that, when the number of sensor nodes is below 150, the mean error decreases rapidly as the node density increases, and when the number of sensor nodes exceeds 170, the mean error remains below 1% as the node density increases. Second, when the number of beacon nodes is less than 60, normal nodes lack sufficient beacon nodes to enable their locations to be estimated. However, the mean error changes slightly as the number of beacon nodes increases above 60. Simulation results revealed that the proposed algorithm for estimating sensor positions is more accurate than existing algorithms, and improves upon conventional bounding box strategies.
- Published
- 2011
42. Optimal design of thermally stable proteins
- Author
-
Vanitha Suresh, Stephen J. Wright, Ryan M. Bannen, George N. Phillips, and Julie C. Mitchell
- Subjects
Statistics and Probability ,Optimal design ,Mathematical optimization ,Materials science ,Protein Conformation ,Entropy ,Configuration entropy ,Protein Engineering ,Biochemistry ,03 medical and health sciences ,Protein structure ,Databases, Protein ,Molecular Biology ,030304 developmental biology ,0303 health sciences ,9. Industry and infrastructure ,030302 biochemistry & molecular biology ,Temperature ,Computational Biology ,Proteins ,Protein engineering ,Directed acyclic graph ,Original Papers ,Structural Bioinformatics ,Computer Science Applications ,Computational Mathematics ,Computational Theory and Mathematics ,Shortest path problem ,Minification ,Biological system ,Dijkstra's algorithm ,Algorithms - Abstract
Motivation: For many biotechnological purposes, it is desirable to redesign proteins to be more structurally and functionally stable at higher temperatures. For example, chemical reactions are intrinsically faster at higher temperatures, so using enzymes that are stable at higher temperatures would lead to more efficient industrial processes. We describe an innovative and computationally efficient method called Improved Configurational Entropy (ICE), which can be used to redesign a protein to be more thermally stable (i.e. stable at high temperatures). This can be accomplished by systematically modifying the amino acid sequence via local structural entropy (LSE) minimization. The minimization problem is modeled as a shortest path problem in an acyclic graph with nonnegative weights and is solved efficiently using Dijkstra's method. Contact: mitchell@biochem.wisc.edu
- Published
- 2008
43. Complex Network Theory Applied to the Growth of Kuala Lumpur’s Public Urban Rail Transit Network
- Author
-
Rui Ding, Hussain Hamid, Jianjun Wu, and Norsidah Ujang
- Subjects
Mathematical optimization ,Urban rail transit ,Computer science ,lcsh:Medicine ,Conservation of Energy Resources ,Betweenness centrality ,Cluster Analysis ,Humans ,Network performance ,Computer Simulation ,lcsh:Science ,Cluster analysis ,Railroads ,Multidisciplinary ,Models, Statistical ,Social network ,business.industry ,lcsh:R ,Malaysia ,Graph theory ,Complex network ,Degree distribution ,Average path length ,Shortest path problem ,lcsh:Q ,Centrality ,business ,Algorithms ,Network analysis ,Research Article - Abstract
Recently, the number of studies involving complex network applications in transportation has increased steadily as scholars from various fields analyze traffic networks. Nonetheless, research on rail network growth is relatively rare. This research examines the evolution of the Public Urban Rail Transit Networks of Kuala Lumpur (PURTNoKL) based on complex network theory and covers both the topological structure of the rail system and future trends in network growth. In addition, network performance when facing different attack strategies is also assessed. Three topological network characteristics are considered: connections, clustering and centrality. In PURTNoKL, we found that the total number of nodes and edges exhibit a linear relationship and that the average degree stays within the interval [2.0488, 2.6774] with heavy-tailed distributions. The evolutionary process shows that the cumulative probability distribution (CPD) of degree and the average shortest path length show good fit with exponential distribution and normal distribution, respectively. Moreover, PURTNoKL exhibits clear cluster characteristics; most of the nodes have a 2-core value, and the CPDs of the centrality's closeness and betweenness follow a normal distribution function and an exponential distribution, respectively. Finally, we discuss four different types of network growth styles and the line extension process, which reveal that the rail network's growth is likely based on the nodes with the biggest lengths of the shortest path and that network protection should emphasize those nodes with the largest degrees and the highest betweenness values. This research may enhance the networkability of the rail system and better shape the future growth of public rail networks.
- Published
- 2015
44. Mining for Candidate Genes Related to Pancreatic Cancer Using Protein-Protein Interactions and a Shortest Path Approach
- Author
-
Fei Yuan, Xiangyin Kong, Sibao Wan, ShaoPeng Wang, and Yu-Hang Zhang
- Subjects
Candidate gene ,Article Subject ,lcsh:Medicine ,Biology ,General Biochemistry, Genetics and Molecular Biology ,law.invention ,Protein–protein interaction ,law ,Pancreatic cancer ,medicine ,Humans ,Protein Interaction Maps ,Gene ,Genetics ,General Immunology and Microbiology ,lcsh:R ,Cancer ,Computational Biology ,General Medicine ,medicine.disease ,Pancreatic Neoplasms ,medicine.anatomical_structure ,Shortest path problem ,Suppressor ,Pancreas ,Algorithms ,Research Article - Abstract
Pancreatic cancer (PC) is a highly malignant tumor derived from pancreas tissue and is one of the leading causes of death from cancer. Its molecular mechanism has been partially revealed by validating its oncogenes and tumor suppressor genes; however, the available data remain insufficient for medical workers to design effective treatments. Large-scale identification of PC-related genes can promote studies on PC. In this study, we propose a computational method for mining new candidate PC-related genes. A large network was constructed using protein-protein interaction information, and a shortest path approach was applied to mine new candidate genes based on validated PC-related genes. In addition, a permutation test was adopted to further select key candidate genes. Finally, for all discovered candidate genes, the likelihood that the genes are novel PC-related genes is discussed based on their currently known functions.
- Published
- 2015
- Full Text
- View/download PDF
45. Hybrid Evolutionary Approaches to Maximum Lifetime Routing and Energy Efficiency in Sensor Mesh Networks
- Author
-
Alma A. M. Rahat, Richard M. Everson, and Jonathan E. Fieldsend
- Subjects
Mathematical optimization ,Computer science ,Node (networking) ,Mesh networking ,Evolutionary algorithm ,Order One Network Protocol ,General Medicine ,Models, Theoretical ,Network topology ,Biological Evolution ,Computational Mathematics ,Shortest path problem ,Routing (electronic design automation) ,Wireless sensor network ,Algorithms ,Efficient energy use - Abstract
Mesh network topologies are becoming increasingly popular in battery-powered wireless sensor networks, primarily because of the extension of network range. However, multihop mesh networks suffer from higher energy costs, and the routing strategy employed directly affects the lifetime of nodes with limited energy resources. Hence when planning routes there are trade-offs to be considered between individual and system-wide battery lifetimes. We present a multiobjective routing optimisation approach using hybrid evolutionary algorithms to approximate the optimal trade-off between the minimum lifetime and the average lifetime of nodes in the network. In order to accomplish this combinatorial optimisation rapidly, our approach prunes the search space using k-shortest path pruning and a graph reduction method that finds candidate routes promoting long minimum lifetimes. When arbitrarily many routes from a node to the base station are permitted, optimal routes may be found as the solution to a well-known linear program. We present an evolutionary algorithm that finds good routes when each node is allowed only a small number of paths to the base station. On a real network deployed in the Victoria & Albert Museum, London, these solutions, using only three paths per node, are able to achieve minimum lifetimes of over 99% of the optimum linear program solution’s time to first sensor battery failure.
- Published
- 2015
46. Multiple Manifold Clustering Using Curvature Constrained Path
- Author
-
Alireza Bayestehtashk, Amir Babaeian, and Mojtaba Bandarabadi
- Subjects
Fuzzy clustering ,Computer science ,Feature vector ,Correlation clustering ,lcsh:Medicine ,Curvature ,Decision Support Techniques ,Pattern Recognition, Automated ,Artificial Intelligence ,CURE data clustering algorithm ,Cluster Analysis ,Humans ,Computer Simulation ,Cluster analysis ,lcsh:Science ,k-medians clustering ,Multidisciplinary ,lcsh:R ,Constrained clustering ,Models, Theoretical ,Graph ,Manifold ,Hierarchical clustering ,Data stream clustering ,ComputingMethodologies_PATTERNRECOGNITION ,Shortest path problem ,Canopy clustering algorithm ,FLAME clustering ,lcsh:Q ,Isomap ,Dijkstra's algorithm ,Algorithm ,Algorithms ,Research Article - Abstract
The problem of multiple surface clustering is a challenging task, particularly when the surfaces intersect. Available methods such as Isomap fail to capture the true shape of the surface near by the intersection and result in incorrect clustering. The Isomap algorithm uses shortest path between points. The main draw back of the shortest path algorithm is due to the lack of curvature constrained where causes to have a path between points on different surfaces. In this paper we tackle this problem by imposing a curvature constraint to the shortest path algorithm used in Isomap. The algorithm chooses several landmark nodes at random and then checks whether there is a curvature constrained path between each landmark node and every other node in the neighborhood graph. We build a binary feature vector for each point where each entry represents the connectivity of that point to a particular landmark. Then the binary feature vectors could be used as a input of conventional clustering algorithm such as hierarchical clustering. We apply our method to simulated and some real datasets and show, it performs comparably to the best methods such as K-manifold and spectral multi-manifold clustering.
- Published
- 2015
47. Directional Navigation Improves Opportunistic Communication for Emergencies
- Author
-
Erol Gelenbe and Andras Kokuti
- Subjects
Technology ,self organization ,Computer science ,EVACUATION ,Real-time computing ,Disaster Planning ,Hazard (computer architecture) ,lcsh:Chemical technology ,Biochemistry ,emergency navigation ,Article ,Analytical Chemistry ,Disasters ,Rescue Work ,Electrochemistry ,Humans ,lcsh:TP1-1185 ,Electrical and Electronic Engineering ,Instrumentation ,Instruments & Instrumentation ,Simulation ,AUTONOMOUS SEARCH ,Science & Technology ,Network packet ,Communication ,Chemistry, Analytical ,Atomic and Molecular Physics, and Optics ,building evacuation ,Chemistry ,SENSOR NETWORKS ,Path (graph theory) ,Shortest path problem ,Physical Sciences ,opportunistic communications ,Emergencies ,Wireless sensor network ,Algorithms - Abstract
We present a novel direction based shortest path search algorithm to guide evacuees during an emergency. It uses opportunistic communications (oppcomms) with low-cost wearable mobile nodes that can exchange packets at close range of a few to some tens of meters without help of an infrastructure. The algorithm seeks the shortest path to exits which are safest with regard to a hazard, and is integrated into an autonomous Emergency Support System (ESS) to guide evacuees in a built environment. The algorithm proposed that ESSs are evaluated with the DBES (Distributed Building Evacuation Simulator) by simulating a shopping centre where fire is spreading. The results show that the directional path finding algorithm can offer significant improvements for the evacuees.
- Published
- 2014
48. Multiple Object Tracking Using the Shortest Path Faster Association Algorithm
- Author
-
Heping Liu, Zhenghao Xi, Huaping Liu, and Bin Yang
- Subjects
Mathematical optimization ,Linear programming ,Article Subject ,Computer science ,lcsh:T ,lcsh:R ,lcsh:Medicine ,General Medicine ,Models, Theoretical ,lcsh:Technology ,General Biochemistry, Genetics and Molecular Biology ,Shortest Path Faster Algorithm ,Robustness (computer science) ,Video tracking ,Shortest path problem ,lcsh:Q ,K shortest path routing ,lcsh:Science ,Algorithm ,Yen's algorithm ,Integer programming ,Algorithms ,General Environmental Science ,Research Article - Abstract
To solve the persistently multiple object tracking in cluttered environments, this paper presents a novel tracking association approach based on the shortest path faster algorithm. First, the multiple object tracking is formulated as an integer programming problem of the flow network. Then we relax the integer programming to a standard linear programming problem. Therefore, the global optimum can be quickly obtained using the shortest path faster algorithm. The proposed method avoids the difficulties of integer programming, and it has a lower worst-case complexity than competing methods but better robustness and tracking accuracy in complex environments. Simulation results show that the proposed algorithm takes less time than other state-of-the-art methods and can operate in real time.
- Published
- 2014
49. An Improved Physarum polycephalum Algorithm for the Shortest Path Problem
- Author
-
Felix T.S. Chan, Andrew Adamatzky, Qing Wang, Xiaoge Zhang, Yong Deng, and Sankaran Mahadevan
- Subjects
Article Subject ,Computer science ,lcsh:T ,Ant colony optimization algorithms ,lcsh:R ,lcsh:Medicine ,General Medicine ,Models, Theoretical ,lcsh:Technology ,General Biochemistry, Genetics and Molecular Biology ,Shortest Path Faster Algorithm ,Physarum polycephalum ,Shortest path problem ,Path (graph theory) ,lcsh:Q ,K shortest path routing ,lcsh:Science ,Algorithm ,Yen's algorithm ,Dijkstra's algorithm ,Algorithms ,Constrained Shortest Path First ,Research Article ,General Environmental Science - Abstract
Shortest path is among classical problems of computer science. The problems are solved by hundreds of algorithms, silicon computing architectures and novel substrate, unconventional, computing devices. Acellular slime mouldP. polycephalumis originally famous as a computing biological substrate due to its alleged ability to approximate shortest path from its inoculation site to a source of nutrients. Several algorithms were designed based on properties of the slime mould. Many of thePhysarum-inspired algorithms suffer from a low converge speed. To accelerate the search of a solution and reduce a number of iterations we combined an original model of Physarum-inspired path solver with a new a parameter, called energy. We undertook a series of computational experiments on approximating shortest paths in networks with different topologies, and number of nodes varying from 15 to 2000. We found that the improvedPhysarumalgorithm matches well with existing Physarum-inspired approaches yet outperforms them in number of iterations executed and a total running time. We also compare our algorithm with other existing algorithms, including the ant colony optimization algorithm and Dijkstra algorithm.
- Published
- 2014
50. Graphs and Matroids Weighted in a Bounded Incline Algebra
- Author
-
Bei Zhang and Ling-Xia Lu
- Subjects
Article Subject ,Weighted matroid ,lcsh:Medicine ,Matroid ,lcsh:Technology ,General Biochemistry, Genetics and Molecular Biology ,Computer Simulation ,lcsh:Science ,General Environmental Science ,Mathematics ,lcsh:T ,lcsh:R ,Numerical Analysis, Computer-Assisted ,General Medicine ,Mathematical Concepts ,Models, Theoretical ,Longest path problem ,Widest path problem ,Algebra ,Graphic matroid ,Shortest path problem ,Matroid partitioning ,lcsh:Q ,Canadian traveller problem ,Algorithms ,Research Article ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Firstly, for a graph weighted in a bounded incline algebra (or called a dioid), a longest path problem (LPP, for short) is presented, which can be considered the uniform approach to the famous shortest path problem, the widest path problem, and the most reliable path problem. The solutions for LPP and related algorithms are given. Secondly, for a matroid weighted in a linear matroid, the maximum independent set problem is studied.
- Published
- 2014
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.