78 results on '"Shortest path problem"'
Search Results
2. Calculation of Fuzzy shortest path problem using Multi-valued Neutrosophic number under fuzzy environment.
- Author
-
Raut, Prasanta Kumar, Behera, Siva Prasad, Broumi, Said, and Mishra, Debdas
- Subjects
- *
GRAPH theory , *GRAPH connectivity , *DIRECTED graphs , *FIRE stations , *TELECOMMUNICATION systems , *SERVICE stations , *FUZZY numbers - Abstract
The most well-known subject in graph theory is the shortest path problem (SPP), which has real-world applications in several different fields of study, including transportation, emergency services, network communications, fire station services, etc. The arc weights of the applicable SP problems are typically represented by fuzzy numbers in real-world applications. In this paper, we discussed the process of finding the shortest distance in a connected graph network in which the arc weights are multi-valued neutrosophic numbers (MNNs). Moreover, here we compare our method with some of the existing results and illustrate one implementation of our method with the help of one numerical example. [ABSTRACT FROM AUTHOR]
- Published
- 2023
3. Calculation of shortest path on Fermatean Neutrosophic Networks.
- Author
-
Raut, Prasanta Kumar, Behera, Siva Prasad, Broumi, Said, and Mishra, Debdas
- Subjects
- *
GRAPH theory - Abstract
The shortest path (SP) problem (SPP) has several applications in graph theory. It can be used to calculate the distance between the provided initial and final vertex in a network. In this paper, we employed the Fermatean neutrosophic number as the appropriate edge weight of the network to estimate the SP connecting the start and end vertex. This technique is highly useful in establishing the shortest path for the decision-maker under uncertainty. We also investigated its effectiveness in comparison to several existing methods. Finally, a few numerical tests were performed to demonstrate the validity and stability of this new technique, as well as to compare different types of shortest paths with different networks. [ABSTRACT FROM AUTHOR]
- Published
- 2023
4. REDUCED SOLUTION SET SHORTEST PATH PROBLEM: CAPTON ALGORITM WITH SPECIAL REFERENCE TO DIJKSTRA'S ALGORITHM.
- Author
-
Abbas, Qaiser, Hussain, Qasim, Zia, Tehseen, and Mansoor, Arfan
- Subjects
PROBLEM solving ,PATHS & cycles in graph theory ,COMPUTER algorithms ,GRAPH theory ,EXISTENCE theorems - Abstract
To find the shortest path between the nodes of a graph, different algorithms like Bellman-Ford, Dijkstra, Floyd-Warshall and Johnson exist. However, in this paper, the issue of shortest path problem with special reference to Dijkstra's algorithm is presented. An idea of shortlisting the appropriate nodes in a graph is proposed and presented, which is then used to find the shortest path with the help of Dijkstra's algorithm. This complete work - named Capton algorithm-provides a solution to single source shortest path problem with minimized time complexity as compared to Dijkstra's algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
5. On the Utilization of Shortest Paths in Complex Networks
- Author
-
Hend Alrasheed
- Subjects
Structure (mathematical logic) ,shortest paths ,Theoretical computer science ,General Computer Science ,small-world phenomenon ,Computer science ,General Engineering ,Graph theory ,Complex network ,Influence maximization (IM) model ,network distance properties ,Network dynamics ,TK1-9971 ,Set (abstract data type) ,network structure ,Shortest path problem ,General Materials Science ,Electrical engineering. Electronics. Nuclear engineering ,Electrical and Electronic Engineering ,Dissemination ,network analysis ,Network analysis - Abstract
Considerable effort has been devoted to the study of network structures and connectivity patterns and their influence on network dynamics. A widely used assumption in network analysis models is that traffic follows the shortest paths connecting pairs of nonneighboring vertices. For example, graph centrality measures, community extraction algorithms, and core-periphery detection algorithms use this assumption. However, this is a very restricted perspective and can be misleading as a consequence of its focus on shortest path communications. In this work, we study the utilization of shortest paths in complex networks in different data dissemination scenarios. We also explore whether there are general properties that can make networks utilize shortest paths more effectively. By conducting simulations on a set of real-world and artificial networks, we show that the utilization of shortest paths in complex networks may not be as common as assumed. This implies that longer paths can be as important (in some cases) as the shortest paths. Our results show that at least two factors clearly influence shortest path utilization in a network: the structure of the network and the data dissemination algorithm. We also find that the type of a network is not a good indicator of its shortest path utilization.
- Published
- 2021
6. On the Shortest Path Game.
- Author
-
Darmann, Andreas, Pferschy, Ulrich, and Schauer, Joachim
- Subjects
- *
GRAPH theory , *DECISION making , *POLYNOMIAL time algorithms , *ACYCLIC model , *DYNAMIC programming - Abstract
In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in each vertex also has to pay the cost of the chosen edge. We want to determine the path where each player minimizes its costs taking into account that also the other player acts in a selfish and rational way. Such a solution is a subgame perfect equilibrium and can be determined by backward induction in the game tree of the associated finite game in extensive form. We show that the decision problem associated with such a path is PSPACE-complete even for bipartite graphs both for the directed and the undirected version. The latter result is a surprising deviation from the complexity status of the closely related game Geography . On the other hand, we can give polynomial time algorithms for directed acyclic graphs and for cactus graphs even in the undirected case. The latter is based on a decomposition of the graph into components and their resolution by a number of fairly involved dynamic programming arrays. Finally, we give some arguments about closing the gap of the complexity status for graphs of bounded treewidth. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
7. A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection
- Author
-
Inmaculada Gutiérrez, Rosa Espínola, Javier Castro, and Daniel Gómez
- Subjects
game theory ,Modularity (networks) ,Theoretical computer science ,Computer science ,General Mathematics ,graph theory ,computational_mathematics ,Measure (physics) ,Graph theory ,Shapley value ,Hierarchical clustering ,hierarchical clustering networks ,Betweenness centrality ,community detection problems ,Shortest path problem ,Computer Science (miscellaneous) ,QA1-939 ,Enhanced Data Rates for GSM Evolution ,Cluster analysis ,Engineering (miscellaneous) ,Game theory ,divisive algorithms ,Mathematics - Abstract
In this paper we formally define the hierarchical clustering network problem (HCNP) as the problem to find a good hierarchical partition of a network. This new problem focuses on the dynamic process of the clustering rather than on the final picture of the clustering process. To address it, we introduce a new hierarchical clustering algorithm in networks, based on a new shortest path betweenness measure. To calculate it, the communication between each pair of nodes is weighed by the importance of the nodes that establish this communication. The weights or importance associated to each pair of nodes are calculated as the Shapley value of a game, named as the linear modularity game. This new measure, (the node-game shortest path betweenness measure), is used to obtain a hierarchical partition of the network by eliminating the link with the highest value. To evaluate the performance of our algorithm, we introduce several criteria that allow us to compare different dendrograms of a network from two point of view: modularity and homogeneity. Finally, we propose a faster algorithm based on a simplification of the node-game shortest path betweenness measure, whose order is quadratic on sparse networks. This fast version is competitive from a computational point of view with other hierarchical fast algorithms, and, in general, it provides better results.
- Published
- 2021
- Full Text
- View/download PDF
8. 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
9. Shortest Paths with Higher-Order Regularization.
- Author
-
Ulen, Johannes, Strandmark, Petter, and Kahl, Fredrik
- Subjects
- *
MATHEMATICAL regularization , *GRAPH theory , *DISCRETIZATION methods , *MATHEMATICAL optimization , *TORSION theory (Algebra) - Abstract
This paper describes a new method of finding thin, elongated structures in images and volumes. We use shortest paths to minimize very general functionals of higher-order curve properties, such as curvature and torsion. Our method uses line graphs to find the optimal path on a given discretization, often in the order of seconds on a single computer. The curves are then refined using local optimization making it possible to recover very smooth curves. We are able to place constraints on our curves such as maximum integrated curvature, or a maximum curvature at any point of the curve. To our knowledge, we are the first to perform experiments in three dimensions with curvature and torsion regularization. The largest graphs we process have over a hundred billion arcs. Experiments on medical images and in multi-view reconstruction show the significance and practical usefulness of higher order regularization. [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
10. A New Graph Theory based Routing Protocol for Wireless Sensor Networks
- Author
-
B. Shanthi and B. Baranidharan
- Subjects
Routing protocol ,business.industry ,Computer science ,Distributed computing ,Graph theory ,Minimum spanning tree ,Data stream clustering ,Shortest path problem ,Scalability ,Computer Science::Networking and Internet Architecture ,Clustering, Energy efficiency, MST, shortest path ,Cluster analysis ,business ,Wireless sensor network ,Computer network - Abstract
Energy efficiency in wireless sensor network [WSN] is the highly sorted area for the researchers. Number of protocols has been suggested for energy efficient information gathering for sensor networks. These protocols come under two broad categories called tree based approach and clustering techniques. In these techniques clustering is more suitable for real time applications and has much more scalability factor when compared with its previous counterpart. This paper presents the importance and factors affecting the clustering. Also this paper surveyed the different clustering algorithms with its extensions till date and proposed the clustering technique using Minimum Spanning Tree [MST] and shortest path concept with its strength and limitations.
- Published
- 2021
- Full Text
- View/download PDF
11. A Novel Method for Network Design and Optimization of District Energy Systems: Considering Network Topology Planning and Pipe Diameter
- Author
-
Yingjun Ruan, Hongyun Liu, Jiazheng Wu, Jiamin Yuan, Shanshan Wang, and Huiming Lu
- Subjects
Mathematical optimization ,Computer science ,020209 energy ,Pipeline (computing) ,graph theory ,district energy system ,02 engineering and technology ,Minimum spanning tree ,minimum spanning tree ,Network topology ,lcsh:Technology ,lcsh:Chemistry ,0202 electrical engineering, electronic engineering, information engineering ,General Materials Science ,pipe diameter grading ,Instrumentation ,lcsh:QH301-705.5 ,network planning ,Fluid Flow and Transfer Processes ,lcsh:T ,Process Chemistry and Technology ,General Engineering ,Graph theory ,lcsh:QC1-999 ,Computer Science Applications ,Pipeline transport ,Network planning and design ,lcsh:Biology (General) ,lcsh:QD1-999 ,lcsh:TA1-2040 ,Shortest path problem ,Path (graph theory) ,020201 artificial intelligence & image processing ,lcsh:Engineering (General). Civil engineering (General) ,lcsh:Physics - Abstract
This paper proposes a new network topology design method that considers all the road nodes, energy stations and load centers to ensure the distribution of pipes along the road. The traditional graph theory and Prim Minimum Spanning Tree (MST) are used to simplify the map and minimize the length of the pipeline. After analyzing the limitations of the traditional network topology model, Point-to-Point (PTP), we present a new model, Energy Station-to-Load Point (ESLP). The model is optimized by minimum cost, not the shortest path. Finally, Pipe Diameter Grading (PDG) is proposed based on ESLP by solving for the pipe diameter that gives the minimum cost under different load demands in the process of optimization. The network design method is effectively applied in a case, and the results show that the path of the optimized plan is 1.88% longer than that of the pre-optimized plan, but the cost is 2.38% lower. The sensitivity analysis shows that the cost of pipeline construction, project life and electricity price all have an impact on the optimization results, and the cost of pipeline construction is the most significant. The difference between the different classifications of pipelines affects whether PDG is effective or not.
- Published
- 2021
12. The STEM Methodology and Graph Theory: Some Practical Examples
- Author
-
Cristina Jordán, Marina Murillo-Arcila, and Juan R. Torregrosa
- Subjects
Theoretical computer science ,Bellman–Ford ,Computer science ,General Mathematics ,weighted graphs ,shortest path algorithms ,Dijkstra ,modeling ,STEM ,Modeling,STEM ,Graph theory ,Shortest path algorithms ,Shortest path problem ,QA1-939 ,Computer Science (miscellaneous) ,Weighted graphs ,Bellman-Ford ,MATEMATICA APLICADA ,Engineering (miscellaneous) ,Dijkstra's algorithm ,Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In this paper, we highlight that Graph Theory is certainly well suited to an applications approach. One of the basic problems that this theory solves is finding the shortest path between two points. For this purpose, we propose two real-world problems aimed at STEM undergraduate students to be solved by using shortest path algorithms from Graph Theory after previous modeling.
- Published
- 2021
- Full Text
- View/download PDF
13. Graph and Network Theory for the Analysis of Criminal Networks
- Author
-
Ovidiu Bagdasar, Giacomo Fiumara, Lucia Cavallaro, Antonio Liotta, and Pasquale De Meo
- Subjects
Social and Information Networks (cs.SI) ,FOS: Computer and information sciences ,Physics - Physics and Society ,Theoretical computer science ,Computer science ,05 social sciences ,Social network analysis (criminology) ,FOS: Physical sciences ,Computer Science - Social and Information Networks ,Graph theory ,Physics and Society (physics.soc-ph) ,02 engineering and technology ,Network theory ,Degree distribution ,Graph ,Shortest path problem ,050501 criminology ,0202 electrical engineering, electronic engineering, information engineering ,Key (cryptography) ,Graph (abstract data type) ,020201 artificial intelligence & image processing ,Social network analysis ,0505 law ,Network model - Abstract
Social Network Analysis is the use of Network and Graph Theory to study social phenomena, which was found to be highly relevant in areas like Criminology. This chapter provides an overview of key methods and tools that may be used for the analysis of criminal networks, which are presented in a real-world case study. Starting from available juridical acts, we have extracted data on the interactions among suspects within two Sicilian Mafia clans, obtaining two weighted undirected graphs. Then, we have investigated the roles of these weights on the criminal network's properties, focusing on two key features: weight distribution and shortest path length. We also present an experiment that aims to construct an artificial network that mirrors criminal behaviours. To this end, we have conducted a comparative degree distribution analysis between the real criminal networks, using some of the most popular artificial network models: Watts-Strogatz, Erd\H{o}s-R\'{e}nyi, and Barab\'{a}si-Albert, with some topology variations. This chapter will be a valuable tool for researchers who wish to employ social network analysis within their own area of interest., Comment: 13 pages, 4 figures. In: Data Science and Internet of Things. Springer, Cham. (2021)
- Published
- 2021
14. Model and algorithm for 4PLRP with uncertain delivery time.
- Author
-
Huang, Min, Ren, Liang, Lee, Loo Hay, Wang, Xingwei, Kuang, Hanbin, and Shi, Haibo
- Subjects
- *
MATHEMATICAL models , *GENETIC algorithms , *DECISION theory , *UNCERTAINTY (Information theory) , *ROUTING (Computer network management) , *GRAPH theory - Abstract
To address the challenge of logistics routing decision under uncertain environment, this paper studies a fourth party logistics routing problem (4PLRP) with uncertain delivery time (4PLRPU). A novel 4PLRPU model based on uncertainty theory is proposed by describing the delivery time of a third party logistics (3PL) provider as an uncertain variable. After that, the model is transformed into an equivalent deterministic model, and several improved genetic algorithms are designed to get solutions. To handle the problem of infeasible solutions in the proposed 4PLRPU, an improved node-based genetic algorithm (INGA) and an improved distance-based genetic algorithm (IDGA) are developed to reduce the computing time required to repair infeasible solutions, and an improved genetic algorithm based on the simple graph and Dijkstra algorithm (SDGA) is proposed to avoid the generation of infeasible solutions. Numerical experiments are conducted to investigate the performance of the proposed algorithms and verify the effectiveness of the proposed 4PLRPU model. The results show that INGA and SDGA are more effective than the standard genetic algorithm and IDGA at solving large-scale problems. Additionally, compared with the expected value model, the 4PLRPU model is more robust. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
15. An Intelligent and Robust Framework towards Anomaly Detection, Medical Diagnosis, and Shortest Path Problems Based on Interval-Valued T-Spherical Fuzzy Information
- Author
-
Syed Khurram Jah Rizvi, Kifayat Ullah, Huanhuan Jin, Naeem Jan, Tahir Mahmood, and Shahzad Saleem
- Subjects
Theoretical computer science ,Article Subject ,Computer science ,General Mathematics ,010102 general mathematics ,Fuzzy set ,General Engineering ,Graph theory ,Context (language use) ,02 engineering and technology ,Interval (mathematics) ,Engineering (General). Civil engineering (General) ,01 natural sciences ,Fuzzy logic ,Shortest path problem ,QA1-939 ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Anomaly detection ,TA1-2040 ,0101 mathematics ,Dijkstra's algorithm ,Mathematics - Abstract
The recent emerging advancements in the domain of the fuzzy sets are the framework of the T-spherical fuzzy set (TSFS) and interval valued T-spherical fuzzy set (IVTSFS). Keeping in view the promising significance of the latest research trend in the fuzzy sets and the enabling impact of IVTSFS, we proposed a novel framework for decision assembly using interval valued TSFS based upon encompassing the four impressive dimensions of human judgement including favor, abstinence, disfavor, and refusal degree. Another remarkable contribution is the optimization of information modeling and prevention of information loss by redefining the concept of each membership in interval. Moreover, the proposed research made a worthy contribution work by demonstrating the effective utilization of the interval valued TSFS based framework in anomaly detection, medical diagnosis, and shortest path problem. The proposed work demonstrates the effective remedial measure for the anomaly detection problem based on several parameters using the aggregation operators of IVTSFS. Moreover, the interval valued T-spherical fuzzy relations and their composition are illustrated to investigate the medical diagnosis problem. Furthermore, the notion of interval valued T-spherical fuzzy graph is also presented and fundamental notions of graph theory are also demonstrated with the help of real world instances. In the context of interval valued T-spherical fuzzy graphs (IVTSFGs), a modified Dijkstra Algorithm (DA) is developed and applied to the shortest path problem. The in-depth quantitative assessment and comparative analysis revealed that the proposed notion outpaces contemporary progressive approaches.
- Published
- 2020
- Full Text
- View/download PDF
16. Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time
- Author
-
Hanlin Ren
- Subjects
FOS: Computer and information sciences ,General Computer Science ,Computer Networks and Communications ,Computer Science::Computational Geometry ,Theoretical Computer Science ,Combinatorics ,Simple (abstract algebra) ,Computer Science - Data Structures and Algorithms ,Data Structures and Algorithms (cs.DS) ,Sensitivity (control systems) ,Computer Science::Data Structures and Algorithms ,Computer Science::Databases ,Mathematics ,Theory of computation → Shortest paths ,Applied Mathematics ,Directed graph ,Data structure ,Vertex (geometry) ,Graph theory ,Computational Theory and Mathematics ,Shortest path problem ,Graph (abstract data type) ,Failure-prone structures ,Constant (mathematics) ,MathematicsofComputing_DISCRETEMATHEMATICS ,Theory of computation → Data structures design and analysis - Abstract
We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph $G=(V, E)$ with edge weights in $\{1, 2, \dots, M\}$, we need to preprocess it into a data structure, and answer the following queries: given vertices $u,v\in V$ and a failed vertex or edge $f\in (V\cup E)$, output the length of the shortest path from $u$ to $v$ that does not go through $f$. Our main result is a simple DSO with $\tilde{O}(n^{2.7233}M)$ preprocessing time and $O(1)$ query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to $\tilde{O}(n^{2.6865}M)$. The preprocessing algorithm is randomized with correct probability $\ge 1-1/n^C$, for a constant $C$ that can be made arbitrarily large. Previously, there is a DSO with $\tilde{O}(n^{2.8729}M)$ preprocessing time and $\operatorname{polylog}(n)$ query time [Chechik and Cohen, STOC'20]. At the core of our DSO is the following observation from [Bernstein and Karger, STOC'09]: if there is a DSO with preprocessing time $P$ and query time $Q$, then we can construct a DSO with preprocessing time $P+\tilde{O}(n^2)\cdot Q$ and query time $O(1)$. (Here $\tilde{O}(\cdot)$ hides $\operatorname{polylog}(n)$ factors.), Comment: journal version
- Published
- 2020
- Full Text
- View/download PDF
17. IMPROVING PATH QUERY PERFORMANCE IN PGROUTING USING A MAP GENERALIZATION APPROACH
- Author
-
R. R. Sankepally and K. S. Rajan
- Subjects
lcsh:Applied optics. Photonics ,Cartographic generalization ,Theoretical computer science ,Computer science ,lcsh:T ,lcsh:TA1501-1820 ,Graph theory ,Topology (electrical circuits) ,02 engineering and technology ,lcsh:Technology ,Bottleneck ,lcsh:TA1-2040 ,020204 information systems ,Path (graph theory) ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,Routing (electronic design automation) ,lcsh:Engineering (General). Civil engineering (General) ,Network model - Abstract
pgRouting library provides functions to compute shortest path between any two points of a road network which is of great demand and also a topic of interest in the field of GIS, graph theory and transportation. To compute path in a road network, pgRouting functions process the entire road network which is a major bottleneck when it comes to routing in large road networks leading to the requirement of large server resources. A reduction/compression in the input network that is to be processed for path computation would improve the performance of pgRouting. In this study a map generalization based network model is proposed which extracts a significantly smaller subset of the road network aka skeleton which further used to divide the network into zones, that shall be selectively used in path computation. This results in processing a much smaller part of the network to compute path between any two points leading to an overall improvement in query performance of pgRouting when computing path, especially on large road networks. As part of assessment of this approach and its applicability to large road networks, the paper presents an in-depth analysis of the trade-offs between deviation in computed path and the performance gain in terms of space and time on road networks of varying sizes and topology to get a better understanding for both providing a sound proof of the utility of the proposed method and also to show its implementability within the current model of pgRouting or any other routing platforms.
- Published
- 2018
18. Percolation approach to simulation of a sustainable network economy structure
- Author
-
Zara R. Alikova, Zarina V. Soskieva, Zaur L. Dzakoev, Mira A. Kantemirova, Sergei R. Chedgemov, Gorsky State Agrarian University, North Ossetian State University, and North Ossetian State Medical Academy
- Subjects
Technological innovations. Automation ,Computer science ,Economics, Econometrics and Finance (miscellaneous) ,JEL: L - Industrial Organization/L.L1 - Market Structure, Firm Strategy, and Market Performance/L.L1.L14 - Transactional Relationships • Contracts and Reputation • Networks ,Management, Monitoring, Policy and Law ,percolation theory ,percolation ,Percolation theory ,Management of Technology and Innovation ,Lattice (order) ,0502 economics and business ,GE1-350 ,Statistical physics ,Business and International Management ,cluster ,[QFIN.GN]Quantitative Finance [q-fin]/General Finance [q-fin.GN] ,[SHS.STAT]Humanities and Social Sciences/Methods and statistics ,05 social sciences ,[INFO.INFO-CE]Computer Science [cs]/Computational Engineering, Finance, and Science [cs.CE] ,HD45-45.2 ,Graph theory ,[SHS.ECO]Humanities and Social Sciences/Economics and Finance ,[QFIN.ST]Quantitative Finance [q-fin]/Statistical Finance [q-fin.ST] ,Network economy ,Network formation ,Environmental sciences ,JEL: D - Microeconomics/D.D8 - Information, Knowledge, and Uncertainty/D.D8.D85 - Network Formation and Analysis: Theory ,networks ,Shortest path problem ,050211 marketing ,Minification ,Conceptual content ,050203 business & management ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
International audience; This study is aimed at the application of the percolation theory to simulation of a sustainable network organization of the economy in conditions of high uncertainty of the external environment. The methods for investment and cost recovery efficiency calculation in order to achieve synergy are used in the course of networks formation. The methods of graph theory and one-dimensional percolation are used herein. The conceptual content of the modified percolation approach to the analysis and simulation of network structures is specified. The controlled process of network formation offers the possibility to form the percolation cluster on the basis of minimization of its length (the shortest path). The formation regularities of two types of a percolation cluster (internal and cross-border) as the basis for the creation of the appropriate network structures are revealed. The examples of the applied problems, which study the percolation based on lattice cells (lattice coupling problem), are considered herein. The results of empirical approbation of the proposed approach in the field of services with the description of the algorithm for the networks and a cluster formation are presented. The transition from the random Bernol's percolation (based on random selection of cells) in favor of the correlated percolation is justified.
- Published
- 2018
19. System principles and evaluation criteria of reliability for optimization of technological parameters of coal deposits
- Author
-
A.О. Khorolskiy and V.H. Grinev
- Subjects
Structure (mathematical logic) ,lcsh:Computer engineering. Computer hardware ,Computer science ,business.industry ,graph theory ,Coal mining ,lcsh:TK7885-7895 ,network model ,Industrial engineering ,the algorithm optimization ,statistical analysis ,lcsh:TA1-2040 ,Shortest path problem ,Selection (linguistics) ,Production (economics) ,the area for the management ,Coal ,Standard algorithms ,business ,lcsh:Engineering (General). Civil engineering (General) ,Network model - Abstract
The article deals with solving the scientific problem of select mining equipment for selection longwall faces of mining venture. The main goal of the paper is to study technology of coal extraction of mining venture. The paper proposes a new approach to solve a problem of mining equipment selection for longwall faces of mining venture. The article describes new method for selection of mining equipment based on theory graph. Special attention is given to technological aspects; they are lenght of longwall faces, depth of coal stratum. Predictions obtained for daily production of mining equipment are compared with design outputs. Conclusions regarding the main reason of instability of longwall faces workings are made. It is found that to be able to use standard algorithms find the shortest path between vertices, you must perform matrix description of the constructed graphs that illustrate the structure of the interaction of different types of control equipment. Using classical optimization of method of discrete mathematics and algorithms for finding the shortest path between two vertices of network models obtained from the formalization of graphs with maximum results of specific types of equipment production chains, solved the problem of rational choice cleaning equipment for the new site with the cost parameters of the mining equipment and cost of mining coal. The authors developed effective and appropriate variants for the mine development for different coal deposits of mining venture.
- Published
- 2017
20. An extended shortest path problem: A data envelopment analysis approach
- Author
-
Amirteimoori, Alireza
- Subjects
- *
GRAPH theory , *COMBINATORICS , *PATHS & cycles in graph theory , *DATA envelopment analysis , *LINEAR programming , *COST analysis , *MATHEMATICAL analysis - Abstract
Abstract: A special and important network structured linear programming problem is the shortest path problem. Classical shortest path problems assume that there are unit of shipping cost or profit along an arc. In many real occasions, various attributes (various costs and profits) are usually considered in a shortest path problem. Because of the frequent occurrence of such network structured problems, there is a need to develop an efficient procedure for handling these problems. This paper studies the shortest path problem in the case that multiple attributes are considered along the arcs. The concept of relative efficiency is defined for each path from initial node to final node. Then, an efficient path with the maximum efficiency is determined. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
21. Hierarchical Motion Planning With Dynamical Feasibility Guarantees for Mobile Robotic Vehicles.
- Author
-
Cowlagi, Raghvendra V. and Tsiotras, Panagiotis
- Subjects
- *
MOBILE robots , *PATHS & cycles in graph theory , *PROBLEM solving , *GRAPH theory , *COMPUTER algorithms , *FEASIBILITY studies - Abstract
Motion planning for mobile vehicles involves the solution of two disparate subproblems: the satisfaction of high-level logical task specifications and the design of low-level vehicle control laws. A hierarchical solution of these two subproblems is efficient, but it may not ensure compatibility between the high-level planner and the constraints that are imposed by the vehicle dynamics. To guarantee such compatibility, we propose a motion-planning framework that is based on a special interaction between these two levels of planning. In particular, we solve a special shortest path problem on a graph at a higher level of planning, and we use a lower level planner to determine the costs of the paths in that graph. The overall approach hinges on two novel ingredients: a graph-search algorithm that operates on sequences of vertices and a lower level planner that ensures consistency between the two levels of hierarchy by providing meaningful costs for the edge transitions of a higher level planner using dynamically feasible, collision-free trajectories. [ABSTRACT FROM PUBLISHER]
- Published
- 2012
- Full Text
- View/download PDF
22. 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
23. Undergraduate Students’ Solutions of Modeling Problems in Algorithmic Graph Theory
- Author
-
Páleníková, Medová, Naštická, and Rybanský
- Subjects
graph algorithms ,Theoretical computer science ,Computer science ,General Mathematics ,graph theory ,MathematicsofComputing_GENERAL ,Minimum spanning tree ,discrete mathematics ,Computer Science (miscellaneous) ,ComputingMilieux_COMPUTERSANDEDUCATION ,0501 psychology and cognitive sciences ,Engineering (miscellaneous) ,Curriculum ,Interpretation (logic) ,lcsh:Mathematics ,05 social sciences ,050301 education ,Graph theory ,error pattern analysis ,lcsh:QA1-939 ,mathematics education ,Test (assessment) ,Hierarchical clustering ,Route inspection problem ,Shortest path problem ,0503 education ,050104 developmental & child psychology - Abstract
Graphs can be considered as useful mathematical models. Graph algorithms are a common part of undergraduate courses in discrete mathematics. Even though they have been successfully implemented in secondary curricula, little research has been dedicated to the analysis of students&rsquo, work. Within a discrete mathematics course for university students, several graph algorithms were introduced via their applications. At the end of the course, the students took a test focused, inter alia, on applications of the algorithms. The mistakes that occurred in 127 students&rsquo, solutions of three problems (the Chinese postman problem, the shortest path problem, and the minimum spanning tree problem) were categorized and compared. Surprisingly, no mistakes were identified in the mathematization of situations or in the interpretation of results with respect to the wording of the problem. The categories of errors varied regardless of the problem types. Hierarchical cluster analysis grouped together the students&rsquo, solutions for the Chinese postman problem and the minimum spanning tree problem. By means of nonparametric item response theory analysis, the Chinese postman problem was identified as the most problematic for students. Possible sources of this difficulty are discussed in more detail herein.
- Published
- 2019
- Full Text
- View/download PDF
24. Radio Map Based Path Planning for Cellular-Connected UAV
- Author
-
Rui Zhang and Shuowen Zhang
- Subjects
Networking and Internet Architecture (cs.NI) ,FOS: Computer and information sciences ,Radio map ,Computer science ,Information Theory (cs.IT) ,Computer Science - Information Theory ,05 social sciences ,050801 communication & media studies ,020206 networking & telecommunications ,Graph theory ,02 engineering and technology ,Grid ,Graph ,Computer Science - Networking and Internet Architecture ,Base station ,0508 media and communications ,Region of interest ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,Motion planning ,Algorithm - Abstract
In this paper, we study the path planning for a cellular-connected unmanned aerial vehicle (UAV) to minimize its flying distance from given initial to final locations, while ensuring a target link quality in terms of the large-scale channel gain with each of its associated ground base stations (GBSs) during the flight. To this end, we propose the use of radio map that provides the information on the large-scale channel gains between each GBS and uniformly sampled locations on a three-dimensional (3D) grid over the region of interest, which are assumed to be time-invariant due to the generally static and large-size obstacles therein (e.g., buildings). Based on the given radio maps of the GBSs, we first obtain the optimal UAV path by solving an equivalent shortest path problem (SPP) in graph theory. To reduce the computation complexity of the optimal solution, we further propose a grid quantization method whereby the grid points in each GBS's radio map are more coarsely sampled by exploiting the spatial channel correlation over neighboring grids. Then, we solve the approximate SPP over the reduced-size radio map (graph) more efficiently. Numerical results show that the proposed solutions can effectively minimize the flying distance of the UAV subject to its communication quality constraint. Moreover, a flexible trade-off between performance and complexity can be achieved by adjusting the quantization ratio for the radio map., to appear in Proc. IEEE Global Communications Conference (Globecom), 2019
- Published
- 2019
25. An efficient multi-objective optimisation method for use in the design of marine protected area networks
- Author
-
C. Gabriela Mayorga Adame, Jeff A. Polton, Alan Fox, Lea-Anne Henry, David Corne, and J. Murray Roberts
- Subjects
0106 biological sciences ,Mathematical optimization ,lcsh:QH1-199.5 ,010504 meteorology & atmospheric sciences ,Computer science ,Population ,Ocean Engineering ,lcsh:General. Including nature conservation, geographical distribution ,Aquatic Science ,random geometric graph ,Oceanography ,01 natural sciences ,Multi-objective optimization ,symbols.namesake ,Pareto optimal solution ,Markov Chain Monte Carlo ,14. Life underwater ,lcsh:Science ,education ,Random geometric graph ,Metaheuristic ,0105 earth and related environmental sciences ,Water Science and Technology ,Global and Planetary Change ,education.field_of_study ,010604 marine biology & hydrobiology ,Graph theory ,Markov chain Monte Carlo ,Marine spatial planning ,multi-objective optimization ,connectivity ,Shortest path problem ,symbols ,lcsh:Q ,marine protected area networks - Abstract
An efficient connectivity-based method for multi-objective optimisation applicable to the design of marine protected area networks is described. Multi-objective network optimisation highlighted previously unreported step changes in the structure of optimal subnetworks for protection associated with minimal changes in cost or benefit functions. This emphasises the desirability of performing a full, unconstrained, multi-objective optimisation for marine spatial planning. Brute force methods, examining all possible combinations of protected and unprotected sites for a network of sites, are impractical for all but the smallest networks as the number of possible networks grows as 2^m, where m is the number of sites within the network. A metaheuristic method based around Markov Chain Monte Carlo methods is described which searches for the set of Pareto optimal networks (or a good approximation thereto) given two separate objective functions, for example for network quality or effectiveness, population persistence, or cost of protection. The optimisation and search methods are independent of the choice of objective functions and can be easily extended to more than two functions. The speed, accuracy and convergence of the method under a range of network configurations are tested with model networks based on an extension of random geometric graphs. Examination of two real-world marine networks, one designated for the protection of the stony coral Lophelia pertusa, the other a hypothetical man-made network of oil and gas installations to protect hard substrate ecosystems, demonstrates the power of the method in finding multi-objective optimal solutions for networks of up to 100 sites. Results using network average shortest path as a proxy for population resilience and gene flow within the network supports the use of a conservation strategy based around highly connected clusters of sites.
- Published
- 2019
26. The Graph Structure of the Internet at the Autonomous Systems Level during Ten Years
- Author
-
Agostino Funel and Funel, Agostino
- Subjects
Networking and Internet Architecture (cs.NI) ,FOS: Computer and information sciences ,Theoretical computer science ,010304 chemical physics ,business.industry ,Computer science ,Computer Science - Networking and Internet Architecture ,Graph theory ,010402 general chemistry ,01 natural sciences ,0104 chemical sciences ,0103 physical sciences ,Shortest path problem ,Graph (abstract data type) ,Hierarchical organization ,Snapshot (computer storage) ,The Internet ,business ,Centrality ,Network analysis - Abstract
We study how the graph structure of the Internet at the Autonomous Systems (AS) level evolved during a decade. For each year of the period 2008-2017 we consider a snapshot of the AS graph and examine how many features related to structure, connectivity and centrality changed over time. The analysis of these metrics provides topological and data traffic information and allows to clarify some assumptions about the models concerning the evolution of the Internet graph structure. We find that the size of the Internet roughly doubled. The overall trend of the average connectivity is an increase over time, while that of the shortest path length is a decrease over time. The internal core of the Internet is composed of a small fraction of big AS and is more stable and connected the external cores. A hierarchical organization emerges where a small fraction of big hubs are connected to many regions with high internal cohesiveness, poorly connected among them and containing AS with low and medium numbers of links. Centrality measurements indicate that the average number of shortest paths crossing an AS or containing a link between two of them decreased over time.
- Published
- 2019
27. Computing Eccentricity Based Topological Indices of Octagonal Grid Omn
- Author
-
Xiujun Zhang, Abdul Qudair Baig, Muhammad Naeem, and Muhammad Kamran Siddiqui
- Subjects
the octagonal grid Omn ,eccentric Zagreb index ,lcsh:Mathematics ,General Mathematics ,Two-graph ,Graph theory ,lcsh:QA1-939 ,Grid ,Graph ,Vertex (geometry) ,Combinatorics ,the octagonal grid O n m ,Topological index ,Shortest path problem ,eccentric connective index ,Computer Science (miscellaneous) ,Astrophysics::Earth and Planetary Astrophysics ,Engineering (miscellaneous) ,connective eccentric index ,Mathematics - Abstract
Graph theory is successfully applied in developing a relationship between chemical structure and biological activity. The relationship of two graph invariants, the eccentric connectivity index and the eccentric Zagreb index are investigated with regard to anti-inflammatory activity, for a dataset consisting of 76 pyrazole carboxylic acid hydrazide analogs. The eccentricity ε v of vertex v in a graph G is the distance between v and the vertex furthermost from v in a graph G. The distance between two vertices is the length of a shortest path between those vertices in a graph G. In this paper, we consider the Octagonal Grid O n m . We compute Connective Eccentric index C ξ ( G ) = ∑ v ∈ V ( G ) d v / ε v , Eccentric Connective Index ξ ( G ) = ∑ v ∈ V ( G ) d v ε v and eccentric Zagreb index of Octagonal Grid O n m , where d v represents the degree of the vertex v in G.
- Published
- 2018
- Full Text
- View/download PDF
28. MODIFIED A* ALGORITHM IMPLEMENTATION IN THE ROUTING OPTIMIZED FOR USE IN GEOSPATIAL INFORMATION SYSTEMS
- Author
-
M. F. Mashhorroudi, S. M. Ayazi, and M. Ghorbani
- Subjects
lcsh:Applied optics. Photonics ,Mathematical optimization ,Computer science ,Equal-cost multi-path routing ,A* search algorithm ,lcsh:Technology ,law.invention ,law ,Yen's algorithm ,lcsh:T ,lcsh:TA1501-1820 ,Graph theory ,Average path length ,Graph ,Longest path problem ,Widest path problem ,Euclidean shortest path ,Private Network-to-Network Interface ,Link-state routing protocol ,Shortest Path Faster Algorithm ,lcsh:TA1-2040 ,Shortest path problem ,K shortest path routing ,Suurballe's algorithm ,Pathfinding ,lcsh:Engineering (General). Civil engineering (General) ,Constrained Shortest Path First - Abstract
Among the main issues in the theory of geometric grids on spatial information systems, is the problem of finding the shortest path routing between two points. In this paper tried to using the graph theory and A* algorithms in transport management, the optimal method to find the shortest path with shortest time condition to be reviewed. In order to construct a graph that consists of a network of pathways and modelling of physical and phasing area, the shortest path routes, elected with the use of the algorithm is modified A*.At of the proposed method node selection Examining angle nodes the desired destination node and the next node is done. The advantage of this method is that due to the elimination of some routes, time of route calculation is reduced.
- Published
- 2018
29. 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
30. Statistical metrics for the characterization of karst network geometry and topology
- Author
-
David Bernasconi, Cécile Vuilleumier, Pauline Collon, Philippe Renard, GeoRessources, Institut national des sciences de l'Univers (INSU - CNRS)-Centre de recherches sur la géologie des matières premières minérales et énergétiques (CREGU)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Centre d'Hydrogéologie et de Géothermie [Neuchâtel] (CHYN), Université de Neuchâtel (UNINE), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre de recherches sur la géologie des matières premières minérales et énergétiques (CREGU)-Institut national des sciences de l'Univers (INSU - CNRS)
- Subjects
topology ,geometry ,010504 meteorology & atmospheric sciences ,Degree (graph theory) ,graph theory ,Statistical parameter ,Graph theory ,010502 geochemistry & geophysics ,Topology ,karst pattern ,01 natural sciences ,karst characterization ,Data set ,Shortest path problem ,Entropy (information theory) ,Data pre-processing ,[SDU.STU.AG]Sciences of the Universe [physics]/Earth Sciences/Applied geology ,Geology ,Geometry and topology ,database ,0105 earth and related environmental sciences ,Earth-Surface Processes - Abstract
International audience; [Update 2021 - Corrigendum in Geomorphology] Statistical metrics can be used to analyse the morphology of natural or simulated karst systems; they allow describing, comparing, and quantifying their geometry and topology. In this paper, we present and discuss a set of such metrics. We study their properties and their usefulness based on a set of more than 30 karstic networks mapped by speleologists. The data set includes some of the largest explored cave systems in the world and represents a broad range of geological and speleogenetic conditions allowing us to test the proposed metrics, their variability, and their usefulness for the discrimination of different morphologies. All the proposed metrics require that the topographical survey of the caves are first converted to graphs consisting of vertices and edges. This data preprocessing includes several quality check operations and some corrections to ensure that the karst is represented as accurately as possible. The statistical parameters relating to the geometry of the system are then directly computed on the graphs, while the topological parameters are computed on a reduced version of the network focusing only on its structure. Among the tested metrics, we include some that were previously proposed such as tortuosity or the Howard's coefficients. We also investigate the possibility to use new metrics derived from graph theory. In total, 21 metrics are introduced, discussed in detail, and compared on the basis of our data set. This work shows that orientation analysis and, in particular, the entropy of the orientation data can help to detect the existence of inception features. The statistics on branch length are useful to describe the extension of the conduits within the network. Rather surprisingly, the tortuosity does not vary very significantly. It could be heavily influenced by the survey methodology. The degree of interconnectivity of the network, related to the presence of maze patterns, can be measured using different metrics such as the Howard's parameters, global cyclic coefficient, or the average vertex degree. The average vertex degree of the reduced graph proved to be the most useful as it is simple to compute, it discriminates properly the interconnected systems (mazes) from the acyclic ones (tree-like structures), and it permits us to classify the acyclic systems as a function of the total number of branches. This topological information is completed by three parameters, allowing us to refine the description. The correlation of vertex degree is rather simple to obtain. It is systematically negative on all studied data sets indicating a predominance of disassortative networks among karst systems. The average shortest path length is related to the transport efficiency. It is shown to be mainly correlated to the size of the network. Finally, central point dominance allows us to identify the presence of a centralized organization.
- Published
- 2017
31. Multiobjective routing in a Metropolitan City with deterministic and dynamic travel and waiting times, and one-way traffic regulation
- Author
-
Chandrasekharan Rajendran, R. Sivanandan, Rainer Leisten, and Swaminathan Vignesh Raja
- Subjects
Mathematical optimization ,Decision support system ,Optimization problem ,Maschinenbau ,Computer science ,Shortest path problem ,Path (graph theory) ,Graph theory ,One-way traffic ,Routing (electronic design automation) ,Linear combination ,Mathematical economics - Abstract
The shortest path problem is the problem of finding one-to-one path from the source to the destination. In real life, the problem involves conflicting and competing objectives, and many researchers solve the multiobjective shortest path optimization problem using a weighted linear combination of objectives. However, the solution of weighted sum is highly sensitive to the weights given, limiting the practicability of this method. Solving the problem by simultaneous optimization of the objective functions to generate a set of nondominated solutions can help to build a decision support system for travelers to choose their own path on the basis of their individual preferences. This chapter proposes a multiobjective mathematical model, solved using e-approach to obtain (heuristically) nondominated solutions of shortest paths with respect to time and distance. In this study, we consider minimizing both distance and time as the objective functions with real-life constraints such as time-dependent dynamic and deterministic travel times, time-dependent dynamic and deterministic waiting times, and time-dependent one-way traffic along the roads. We implement the proposed model by using the real-life planning data (1658 nodes and 4224 links) of Chennai city network (a metropolitan city in India with highly interconnected network of roads), and present the discussion on the multiobjective routing problem with real-life considerations.
- Published
- 2017
32. Generating time-varying road network data using sparse trajectories
- Author
-
Hakan Ferhatosmanoglu, Bahaeddin Eravci, Josep L. Larriba-Pey, Elif Eser, and Furkan Kocayusufoglu
- Subjects
Time dependent shortest paths ,Graph databases ,Theoretical computer science ,HE ,Computer science ,Transportation ,02 engineering and technology ,computer.software_genre ,Time-varying graphs ,QA76 ,0202 electrical engineering, electronic engineering, information engineering ,Dynamic road networks ,Frequency domain analysis ,Data mining ,Sparse matrix ,020203 distributed computing ,Graph database ,Wait-for graph ,Time-dependent shortest paths ,Complete graph ,Real time systems ,Roads and streets ,Graph ,Graph theory ,Motor transportation ,Database systems ,Shortest path problem ,Algorithm design ,Data generation ,Time varying networks ,computer - Abstract
Date of Conference: 12-15 Dec. 2016 Conference name: IEEE 16th International Conference on Data Mining Workshops (ICDMW), 2016 While research on time-varying graphs has attracted recent attention, the research community has limited or no access to real datasets to develop effective algorithms and systems. Using noisy and sparse GPS traces from vehicles, we develop a time-varying road network data set where edge weights differ over time. We present our methodology and share this dataset, along with a graph manipulation tool. We estimate the traffic conditions using the sparse GPS data available by characterizing the sparsity issues and assessing the properties of travel sequence data frequency domain. We develop interpolation methods to complete the sparse data into a complete graph dataset with realistic time-varying edge values. We evaluate the performance of time-varying and static shortest path solutions over the generated dynamic road network. The shortest paths using the dynamic graph produce very different results than the static version. We provide an independent Java API and a graph database to analyze and manipulate the generated time-varying graph data easily, not requiring any knowledge about the inners of the graph database system. We expect our solution to support researchers to pursue problems of time-varying graphs in terms of theoretical, algorithmic, and systems aspects. The data and Java API are available at: http://elif.eser.bilkent.edu.tr/roadnetwork. © 2016 IEEE.
- Published
- 2016
33. Minimum Eccentricity Shortest Path Problem: an Approximation Algorithm and Relation with the k-Laminarity Problem
- Author
-
Fabien de Montgolfier, Léo Planche, Etienne Birmelé, Mathématiques Appliquées Paris 5 (MAP5 - UMR 8145), Université Paris Descartes - Paris 5 (UPD5)-Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), MAC2 (Idex USPC), MAC2, Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Mathématiques Appliquées à Paris 5 ( MAP5 - UMR 8145 ), Université Paris Descartes - Paris 5 ( UPD5 ) -Institut National des Sciences Mathématiques et de leurs Interactions-Centre National de la Recherche Scientifique ( CNRS ), Institut de Recherche en Informatique Fondamentale ( IRIF ), Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ), Networks, Graphs and Algorithms ( GANG ), Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria de Paris, and Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria )
- Subjects
FOS: Computer and information sciences ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,k-Laminar Graph ,BFS ,Discrete Mathematics (cs.DM) ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,Computational Complexity (cs.CC) ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Graph search ,01 natural sciences ,Eccentricity ,Combinatorics ,Diameter ,0202 electrical engineering, electronic engineering, information engineering ,Yen's algorithm ,[ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Mathematics ,Discrete mathematics ,[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM] ,Longest path problem ,Widest path problem ,Graph theory ,Computer Science - Computational Complexity ,Euclidean shortest path ,[ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC] ,Shortest Path Faster Algorithm ,010201 computation theory & mathematics ,Shortest path problem ,020201 artificial intelligence & image processing ,K shortest path routing ,Approximation Algorithms ,Distance ,Computer Science - Discrete Mathematics - Abstract
International audience; The Minimum Eccentricity Shortest Path (MESP) Problem consists in determining a shortest path (a path whose length is the distance between its extremities) of minimum eccentricity in a graph. It was introduced by Dragan and Leitert [9] who described a linear-time algorithm which is an 8-approximation of the problem. In this paper, we study deeper the double-BFS procedure used in that algorithm and extend it to obtain a linear-time 3-approximation algorithm. We moreover study the link between the MESP problem and the notion of laminarity, introduced by Völkel et al [12], corresponding to its restriction to a diameter (i.e. a shortest path of maximum length), and show tight bounds between MESP and laminarity parameters.
- Published
- 2016
34. The development of e-learning applications solving problems from graph theory
- Author
-
Pavel Kolman, Petr Zach, and Josef Holoubek
- Subjects
Theoretical computer science ,Linear programming ,business.industry ,graph theory ,lcsh:S ,Graph theory ,Minimum spanning tree ,Modular design ,Delphi ,lcsh:Agriculture ,lcsh:Biology (General) ,Shortest path problem ,General Agricultural and Biological Sciences ,business ,computer ,Critical path method ,optimization ,lcsh:QH301-705.5 ,Network analysis ,Mathematics ,computer.programming_language ,operations research - Abstract
Authors are in long term developing e-learning supports for some parts of Operation Research course. The original purpose was to prepare e-learning supports for students of FBE Mendelu, mainly for part-time form students, who have subscribed Economic mathematical methods course (EMM). Considering decreasing number of lessons on part-time form of study (16 hours in a semester, in comparison to 56 hours in full-time form of study), was for part-time form students even more difficult to fulfill exam requirements. As a help for students there was stage by stage prepared several of programs, they allow self-contained practicing of some linear programming methods. Programs did allow to users step-by-step verify their solution, i.e. whether their calculation are in accordance with algorithm described in lectures. Advantage for the students consists in fact, that each mistake (numerical or algorithmic) they were able to uncover, what contributes to increase of self-study effectiveness and from that resulting higher study motivation. Resulting from existing experience, authors decided to request for a new FRVS grant for academic year 2012, focused on e-learning support of selected graph theory problems. Within this project there was developed a tool allowing to make and according to the user needs interactively modify created graphs. On this graph it is possible individually, step by step (in compliance with on lectures presented algorithm) to practice solving of selected graph theory and network analysis problems (e.g. minimal spanning tree, shortest path in a graph, testing for cycles in a graph, critical path method etc.). Project is realized as modular and was realized in Delphi developing tool. Described algorithms are saved in dynamic linked libraries. There for it is very easy to add here new (newly programmed) algorithms. Project results (i.e. project experience obtained from e-learning supports) will be available for all FBE Mendelu members interested in this problematic.
- Published
- 2013
35. Constructing Large-scale Low-latency Network from Small Optimal Networks
- Author
-
Ryosuke Mizuno and Yawara Ishida
- Subjects
020203 distributed computing ,Small diameter ,Theoretical computer science ,Mathematical problem ,Computer science ,Graph theory ,0102 computer and information sciences ,02 engineering and technology ,Reuse ,01 natural sciences ,Electronic mail ,Graph ,010201 computation theory & mathematics ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,FOS: Mathematics ,Mathematics - Combinatorics ,Hypercube ,Combinatorics (math.CO) ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
The construction of large-scale, low-latency networks becomes difficult as the number of nodes increases. In general, the way to construct a theoretically optimal solution is unknown. However, it is known that some methods can construct suboptimal networks with low-latency. One such method is to construct large-scale networks from optimal or suboptimal small networks, using the product of graphs. There are two major advantages to this method. One is that we can reuse small, already known networks to construct large-scale networks. The other is that the networks obtained by this method have graphtheoretical symmetry, which reduces the overhead of communication between nodes. A network can be viewed as a "graph", which is a mathematical term from combinatorics. The design of low-latency networks can be treated as a mathematical problem of finding small diameter graphs with a given number of nodes ( called "order" ) and a given number of connections between each node ( called "degree" ). In this paper, we overview how to construct large graphs from optimal or suboptimal small graphs by using graph-theoretical products. We focus on the case of diameter 2 in particular. As an example, we introduce a graph of order 256, degree 22 and diameter 2, which granted us the Deepest Improvement Award at the "Graph Golf" competition. Moreover, the average shortest path length of the graph is the smallest in graphs of order 256 and degree 22.
- Published
- 2016
36. ASSESSMENT OF AKURE ROAD NETWORK: A SHORTEST PATH APPROACH
- Author
-
Olufikayo Aderinlewo, Seun Daniel Oluwajana, Adebayo Oladipo Owolabi, and Silvana Croope
- Subjects
shortest path ,Mathematical optimization ,Computer science ,lcsh:T ,graph theory ,primal approach ,edge length distribution ,lcsh:Technology ,efficiency ,lcsh:TA1-2040 ,Shortest path problem ,shortest path, primal approach, graph theory, edge length distribution, efficiency ,lcsh:Engineering (General). Civil engineering (General) ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In this paper, the road network of Akure (a city in south western Nigeria) was studied based on its shortest path properties. Three sections, each measuring 1 square mile, were sampled from the entire road network and developed into graphs using both a primal approach and graph theory in which the intersections and streets were represented as nodes and edges respectively. These graphs were assessed for the edge lengths and shortest paths between nodes from which their edge length distributions, average path lengths and efficiencies were also obtained. It was concluded that the city of Akure is self-organized with small world properties since the network case studies showed small path lengths.
- Published
- 2016
37. Parallel Voronoi Computation for Physics-Based Simulations
- Author
-
Julio Toss, Joao Comba, Bruno Raffin, Instituto de Informática da UFRGS (UFRGS), Universidade Federal do Rio Grande do Sul [Porto Alegre] (UFRGS), Data Aware Large Scale Computing (DATAMOVE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), and Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])
- Subjects
General Computer Science ,Computer science ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,General Engineering ,020207 software engineering ,Graph theory ,02 engineering and technology ,Computational geometry ,01 natural sciences ,[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation ,Computational science ,Bowyer–Watson algorithm ,0103 physical sciences ,Shortest path problem ,0202 electrical engineering, electronic engineering, information engineering ,Graph (abstract data type) ,Algorithm design ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,010306 general physics ,Voronoi diagram ,Dijkstra's algorithm ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
International audience; Voronoi diagrams are fundamental data structures in computational geometry, with applications in such areas as physics-based simulations. For non-Euclidean distances, the Voronoi diagram must be performed over a grid-graph, where the edges encode the required distance information. Th e major bottleneck in this case is a shortest path algorithm that must be computed multiple times during the simulation. We present a GPU algorithm for solving the shortest path problem from multiple sources using a generalized distance function. Our algorithm was designed to leverage the grid-based nature of the underlying graph that represents the deformable objects. Experimental results report speed-ups up to 65× over a current reference sequential method.
- Published
- 2016
38. Determining structural route components from GPS traces
- Author
-
Tom Bellemans, Luk Knapen, Irith Ben-Arroyo Hartman, Geert Wets, Davy Janssens, Daniel Schulz, and Publica
- Subjects
050210 logistics & transportation ,Mathematical optimization ,021103 operations research ,business.industry ,Travel behavior ,Route choice ,Route decomposition ,Transportation modeling ,GPS traces ,Graph theory ,05 social sciences ,0211 other engineering and technologies ,Traffic simulation ,Transportation ,02 engineering and technology ,Map matching ,Directed graph ,Management Science and Operations Research ,Flow network ,0502 economics and business ,Path (graph theory) ,Shortest path problem ,Global Positioning System ,business ,Algorithm ,Civil and Structural Engineering ,Mathematics - Abstract
Analysis of GPS traces shows that people often do not use the least cost path through the transportation network while making trips. This leads to the question which structural path characteristics can be used to construct realistic route choice sets for use in traffic simulation models. In this paper, we investigate the hypothesis that, for utilitarian trips, the route between origin and destination consists of a small number of concatenated least cost paths. The hypothesis is verified by analyzing routes extracted from large sets of recorded GPS traces which constitute revealed preference information. Trips have been extracted from the traces and for each trip the path in the transportation network is determined by map matching. This is followed by a path decomposition phase for which the algorithm constitutes the first contribution of this paper. There are multiple ways to split a given path in a directed graph into a minimal number of subpaths of minimal cost By calculating two specific path splittings, it is possible to identify subsets of the vertices (splitVertexSuites) that can be used to generate every possible minimum path splitting by taking one vertex from each such subset As a second contribution, we show how the extracted information is used in microscopic travel simulation. The distribution for the size of the minimum decomposition, extracted from the GPS traces, can be used in constrained enumeration methods for route choice set generation. The sets of vertices that can act as boundary vertices separating consecutive route parts contain way points (landmarks) having a particular meaning to their user. The paper explains the theoretical aspects of route splitting as well as the process to extract splitVertexSuites from big data. It reports statistical distributions extracted from sets of GPS traces for both multimodal person movements and unimodal car trips. The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement nr 270833.
- Published
- 2016
39. A Flexible Methodology to Sectorize Water Supply Networks Based on Social Network Theory Concepts and on Multi-objective Optimization
- Author
-
M. Tavera, Amilkar E. Ilaya-Ayza, Enrique Campbell, Joaquín Izquierdo, Rafael Pérez-García, and Idel Montalvo
- Subjects
Optimization ,Atmospheric Science ,Engineering ,Mathematical optimization ,INGENIERIA HIDRAULICA ,Process (engineering) ,Reliability (computer networking) ,0208 environmental biotechnology ,Water supply ,02 engineering and technology ,Multi-objective optimization ,Sectorization ,Civil and Structural Engineering ,Water Science and Technology ,Community detection ,business.industry ,Swarm behaviour ,Graph theory ,Geotechnical Engineering and Engineering Geology ,Reliability ,020801 environmental engineering ,Core (game theory) ,Shortest path problem ,business ,MATEMATICA APLICADA ,Sectors - Abstract
A novel methodology to sectorize water supply networks (WSNs) depending on a main transmission line is presented in this paper. The methodology is based on concepts derived from the social network theory and graph theory (namely, community detection and shortest path respectively); and also on a multi-objective optimization process by means of agent swarm optimization (ASO). A series of energy, operative, and economic criteria are optimized in this process. The core idea is to form sectors over the distribution network based on communities found using a community detection algorithm (Walktrap). The methodology is flexible and enables the technical staff in water utilities to make decisions at different stages. It has been tested by generating four feasible solutions over a portion of a real WSN.
- Published
- 2016
- Full Text
- View/download PDF
40. 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
41. Un problema a resolver con los algoritmos de caminos más cortos
- Author
-
Cristina Jordán, Raquel Herráiz, and Jordi Burriel
- Subjects
Theoretical computer science ,business.industry ,Large numbers ,Graph theory ,Algoritmo de Floyd ,Large range ,Type (model theory) ,Problema camino más cortos ,lcsh:Education (General) ,Exponential function ,Shortest path problem ,Graph (abstract data type) ,Order (group theory) ,Artificial intelligence ,business ,lcsh:L7-991 ,Grafo ponderado ,Mathematics - Abstract
[EN] Graph theory solves, via a good modelization, a very large number of problems in different areas. This is why, this theory has been having an exponential increase in the last years. One of the basic problems that this theory solves is to obtain the shortest path between two points. In order to illustrate this problem, to motivate its study and to introduce the student in the world of the mathematical modelization and its large range of possibilities, we present a specific case: to help the police to catch the authors of a theft. The solution consists of representing the city where it took place by a no directed positive weighted graph and to apply the Floyd’s algorithm mixed with a reasoning of combinatorial type. At the end of the exercise, we can assure that the thieves cannot escape, by using another concept of graph theory, the vertex-cut., [ES] Numerosos problemas pertenecientes a los más diversos campos pueden ser resueltos a partir de la modelización en teoría de grafos, materia en pleno auge, podríamos decir que con crecimiento exponencial, por su amplia aplicabilidad. Uno de los primeros problemas que se plantean al alumno que inicia el estudio de la teoría de grafos es el cálculo del trazado de un camino de mínimo peso de un vértice a otro, es decir, el cálculo de la distancia mínima que separa dos vértices dados, así como el recorrido a realizar para obtenerla. Para ilustrarlo, motivar su estudio e iniciar al estudiante en el mundo de la modelización y su amplia gama de posibilidades, presentamos el siguiente caso concreto, en el que ayudamos a la policía a atrapar a los autores de un robo. La solución consiste en representar la ciudad en la que tiene lugar el atraco mediante un grafo no dirigido ponderado positivo, y aplicar el algoritmo de Floyd, entrelazado con razonamientos de tipo combinatorio. Podremos asegurar al final del ejercicio que los ladrones no tienen escapatoria, relacionando la solución con otro concepto de la teoría de grafos, la cortadura de vértices.
- Published
- 2011
42. Modulus on graphs as a generalization of standard graph theoretic quantities
- Author
-
Roberto Perez, Natalie Wiens, Megan Brunner, Pietro Poggi-Corradini, and Nathan Albin
- Subjects
Discrete mathematics ,Graph theoretic ,Generalization ,Maximum flow problem ,Modulus ,Graph theory ,Optimization and Control (math.OC) ,Shortest path problem ,FOS: Mathematics ,Mathematics - Combinatorics ,05C85, 90C35 ,Geometry and Topology ,Combinatorics (math.CO) ,Mathematics - Optimization and Control ,Mathematics - Abstract
This paper presents new results for the modulus of families of walks on a graph---a discrete analog of the modulus of curve families due to Beurling and Ahlfors. Particular attention is paid to the dependence of the modulus on its parameters. Modulus is shown to generalize (and interpolate among) three important quantities in graph theory: shortest path, effective resistance, and max-flow or min-cut., Updated with referee's comments. To appear in ECGD
- Published
- 2015
43. Compromising system and user interests in shelter location and evacuation planning
- Author
-
Barbaros Ç. Tansel, Hande Yaman, and Vedat Bayram
- Subjects
Engineering ,Travel time ,System-optimal ,Operations research ,Traffic control ,shelter ,Poison control ,Transportation ,Management Science and Operations Research ,Transport engineering ,Constrained System Optimal ,Constrained systems ,Second Order Cone Programming ,Point (geometry) ,Evacuation Traffic Management ,Nonlinear mixed integer programming ,Integer programming ,Civil and Structural Engineering ,Shelter locations ,Economic and social effects ,business.industry ,Traffic management ,System optimal ,Evacuation plan ,Shelter Location ,Emergency traffic control ,Traffic Assignment System Optimal ,Graph theory ,Second-order cone programming ,hazard management ,Shortest path problem ,Traffic assignment ,business ,numerical model ,Decision making ,optimization - Abstract
Cataloged from PDF version of article. Traffic management during an evacuation and the decision of where to locate the shelters are of critical importance to the performance of an evacuation plan. From the evacuation management authority’s point of view, the desirable goal is to minimize the total evacuation time by computing a system optimum (SO). However, evacuees may not be willing to take long routes enforced on them by a SO solution; but they may consent to taking routes with lengths not longer than the shortest path to the nearest shelter site by more than a tolerable factor. We develop a model that optimally locates shelters and assigns evacuees to the nearest shelter sites by assigning them to shortest paths, shortest and nearest with a given degree of tolerance, so that the total evacuation time is minimized. As the travel time on a road segment is often modeled as a nonlinear function of the flow on the segment, the resulting model is a nonlinear mixed integer programming model. We develop a solution method that can handle practical size problems using second order cone programming techniques. Using our model, we investigate the importance of the number and locations of shelter sites and the trade-off between efficiency and fairness. 2014 Elsevier Ltd. All rights reserved.
- Published
- 2015
44. TPA: A Two-Phase Approach Using Simulated Annealing for the Optimization of Census Taker Routes in Mexico
- Author
-
Silvia Gaona and David Romero
- Subjects
Optimization ,Visibility graphs ,Travel distance ,Two phase approach ,Shortest path ,Two phase ,Article Subject ,Computer science ,General Mathematics ,Surveys ,Machine learning ,computer.software_genre ,Simulated annealing ,business.industry ,Heuristic ,lcsh:Mathematics ,Visibility graph ,Second phase ,General Engineering ,Dijkstra's algorithms ,Census ,lcsh:QA1-939 ,Graph ,Graph theory ,7 INGENIERÍA Y TECNOLOGÍA ,lcsh:TA1-2040 ,Me-xico ,Shortest path problem ,Graph (abstract data type) ,Artificial intelligence ,lcsh:Engineering (General). Civil engineering (General) ,business ,Dijkstra's algorithm ,computer ,Algorithm - Abstract
Censuses in Mexico are taken by the National Institute of Statistics and Geography (INEGI). In this paper a Two-Phase Approach (TPA) to optimize the routes of INEGI’s census takers is presented. For each pollster, in the first phase, a route is produced by means of the Simulated Annealing (SA) heuristic, which attempts to minimize the travel distance subject to particular constraints. Whenever the route is unrealizable, it is made realizable in the second phase by constructing a visibility graph for each obstacle and applying Dijkstra’s algorithm to determine the shortest path in this graph. A tuning methodology based on theiracepackage was used to determine the parameter values for TPA on a subset of 150 instances provided by INEGI. The practical effectiveness of TPA was assessed on another subset of 1962 instances, comparing its performance with that of the in-use heuristic (INEGIH). The results show that TPA clearly outperformsINEGIH. The average improvement is of 47.11%.
- Published
- 2015
- Full Text
- View/download PDF
45. Non-linear pricing by convex duality
- Author
-
Mustafa Ç. Pınar
- Subjects
Optimization ,Mathematical optimization ,Computer Science::Computer Science and Game Theory ,Shortest path problem ,Optimization problem ,Regularity assumption ,Asymmetric information ,Shortest path ,Economics ,Shortest paths ,Mechanism design ,Duality (optimization) ,Nonlinear utility functions ,Nonlinear pricing ,Differentiable function ,Electrical and Electronic Engineering ,Mathematics ,Non-linear pricing ,Function (mathematics) ,Sales ,Convex optimization ,Costs ,Graph theory ,Probability distributions ,Control and Systems Engineering ,Machine design ,Probability distribution ,Optimization problems - Abstract
We consider the pricing problem of a risk-neutral monopolist who produces (at a cost) and offers an infinitely divisible good to a single potential buyer that can be of a finite number of (single dimensional) types. The buyer has a non-linear utility function that is differentiable, strictly concave and strictly increasing. Using a simple reformulation and shortest path problem duality as in Vohra (2011) we transform the initial non-convex pricing problem of the monopolist into an equivalent optimization problem yielding a closed-form pricing formula under a regularity assumption on the probability distribution of buyer types. We examine the solution of the problem when the regularity condition is relaxed in different ways, or when the production function is non-linear and convex. For arbitrary type distributions, we offer a complete solution procedure.
- Published
- 2015
46. Cellular Automata Based Real-time Path-planning for Mobile Robots
- Author
-
Faraz Kunwar, Syed Usman Ahmed, and Arsalan Akhter
- Subjects
Computer science ,Distributed computing ,lcsh:Electronics ,lcsh:TK7800-8360 ,Mobile robot ,Graph theory ,Optimal control ,Motion control ,Any-angle path planning ,Cellular automaton ,lcsh:QA75.5-76.95 ,Computer Science Applications ,Artificial Intelligence ,Shortest path problem ,Obstacle avoidance ,Motion planning ,lcsh:Electronic computers. Computer science ,Software - Abstract
Intelligent mobile robotic agents demand optimal motion planners with minimal query time. Most contemporary algorithms lack one of these two required aspects. This paper proposes an efficient path-planning scheme based on cellular automata (CA) that generates optimal paths in the minimum time. A Cellular automaton is evolved over the entire search space and subsequently used for the determination of the shortest path. This approach generates a parent-child relationship for each cell in order to minimize the search time. Performance comparisons with A*, Dijkstra's, D* and MPCNN have proven it to be time-efficient. Analysis, simulation and experimental results have proven it to be a robust and complete path-planning scheme. Also it has demonstrated to be time-efficient in both static and dynamic environments.
- Published
- 2014
47. Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems
- Author
-
B. V. Rao, Bodo Manthey, Christian Engels, Karl Bringmann, and Discrete Mathematics and Mathematical Programming
- Subjects
FOS: Computer and information sciences ,Metric spaces ,General Computer Science ,Average case analysis ,Travelling salesman problem ,Combinatorics ,Traveling Salesman Problem ,IR-96314 ,Computer Science - Data Structures and Algorithms ,Data Structures and Algorithms (cs.DS) ,EWI-24792 ,Mathematics ,METIS-312441 ,Discrete mathematics ,Random graph ,Applied Mathematics ,Random function ,Approximation algorithm ,random metric spaces ,Approximation algorithms ,Computer Science Applications ,Euclidean shortest path ,Metric space ,Graph theory ,Probability distributions ,Solvents ,Traveling salesman problem ,Approximation ratios ,Euclidean instances ,First passage percolation ,K-median problem ,Optimization problems ,Probabilistic analysis ,Random metrics ,Shortest path ,Optimization ,Shortest path problem ,Metric (mathematics) ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Probabilistic analysis for metric optimization problems has mostly been conducted on random Euclidean instances, but little is known about metric instances drawn from distributions other than the Euclidean. This motivates our study of random metric instances for optimization problems obtained as follows: Every edge of a complete graph gets a weight drawn independently at random. The distance between two nodes is then the length of a shortest path (with respect to the weights drawn) that connects these nodes. We prove structural properties of the random shortest path metrics generated in this way. Our main structural contribution is the construction of a good clustering. Then we apply these findings to analyze the approximation ratios of heuristics for matching, the traveling salesman problem (TSP), and the k-median problem, as well as the running-time of the 2-opt heuristic for the TSP. The bounds that we obtain are considerably better than the respective worst-case bounds. This suggests that random shortest path metrics are easy instances, similar to random Euclidean instances, albeit for completely different structural reasons., To appear in Algorithmica
- Published
- 2013
48. Simulation of Obstruction Avoidance Generously Mobility (OAGM) Model using Graph-theory Technique
- Author
-
M. Hemalatha and V. Vasanthi
- Subjects
Networking and Internet Architecture (cs.NI) ,FOS: Computer and information sciences ,Mobility model ,General Computer Science ,Computer science ,Distributed computing ,Node (networking) ,Mission critical ,General Engineering ,Process (computing) ,Graph theory ,Computer Science - Networking and Internet Architecture ,Obstacle ,Shortest path problem ,Wireless sensor network - Abstract
An Obstruction Avoidance Generously Mobility (OAGM) model has been introduced for controlling ad-hoc sensor networks and thereby operating emerging fields like military and healthcare services. According to this model, the ability to send a message to a group of users simultaneously, based solely on their geographic location, is desirable by using Mission Critical Mobility model that assumes the obstacle shapes like rectangle or square in the simulation terrain. The OAGM model is developed by grasping the critical situations of military and healthcare services by incorporating the node movement model, hierarchical node organization, placement of obstacle that affect the movement of nodes and also signal propagation. Graph theory technique is used to find the shortest path of the node movement process. The varying number of parameter sets with DSR protocol is analyzed for MCM and OAGM mobility model. The results show OAGM performance is better than MCM., 9 pages
- Published
- 2013
49. The Difference of Brain Functional Connectivity between Eyes-Closed and Eyes-Open Using Graph Theoretical Analysis
- Author
-
Bo Tan, Xianxian Kong, Ling Li, Zhenlan Jin, and Ping Yang
- Subjects
Male ,Article Subject ,Rest ,Models, Neurological ,Alpha (ethology) ,Electroencephalography ,lcsh:Computer applications to medicine. Medical informatics ,General Biochemistry, Genetics and Molecular Biology ,Combinatorics ,Young Adult ,Statistics ,medicine ,Humans ,Beta (finance) ,Ocular Physiological Phenomena ,Mathematics ,Likelihood Functions ,Models, Statistical ,General Immunology and Microbiology ,Resting state fMRI ,medicine.diagnostic_test ,Applied Mathematics ,Functional connectivity ,Brain ,Computational Biology ,Graph theory ,General Medicine ,Human brain ,medicine.anatomical_structure ,Modeling and Simulation ,Shortest path problem ,lcsh:R858-859.7 ,Female ,Nerve Net ,Algorithms ,Research Article - Abstract
To study the differences in functional brain networks between eyes-closed (EC) and eyes-open (EO) at resting state, electroencephalographic (EEG) activity was recorded in 21 normal adults during EC and EO states. The synchronization likelihood (SL) was applied to measure correlations between all pairwise EEG channels, and then the SL matrices were converted to graphs by thresholding. Graphs were measured by topological parameters in theta (4–7 Hz), alpha (8–13 Hz), and beta (14–30 Hz) bands. By changing from EC to EO states, mean cluster coefficients decreased in both theta and alpha bands, but mean shortest path lengths became shorter only in the alpha band. In addition, local efficiencies decreased in both theta and alpha bands, while global efficiencies in the alpha band increased inversely. Opening the eyes decreased both nodes and connections in frontal area in the theta band, and also decreased those in bilateral posterior areas in the alpha band. These results suggested that a combination of the SL and graph theory methods may be a useful tool for distinguishing states of EC and EO. The differences in functional connectivity between EC and EO states may reflect the difference of information communication in human brain.
- Published
- 2013
50. BootGraph: Probabilistic fiber tractography using bootstrap algorithms and graph theory
- Author
-
Robert S. Vorburger, Peter Boesiger, Carolin Reischauer, University of Zurich, and Vorburger, Robert S
- Subjects
2805 Cognitive Neuroscience ,Brain Mapping ,Cognitive Neuroscience ,Probabilistic logic ,Graph theory ,610 Medicine & health ,Cone of Uncertainty ,Data set ,170 Ethics ,Diffusion Magnetic Resonance Imaging ,Diffusion Tensor Imaging ,Neurology ,2808 Neurology ,Shortest path problem ,Image Processing, Computer-Assisted ,Graph (abstract data type) ,Humans ,10237 Institute of Biomedical Engineering ,Algorithm ,Algorithms ,Diffusion MRI ,Mathematics ,Tractography ,Probability - Abstract
Bootstrap methods have recently been introduced to diffusion-weighted magnetic resonance imaging to estimate the measurement uncertainty of ensuing diffusion parameters directly from the acquired data without the necessity to assume a noise model. These methods have been previously combined with deterministic streamline tractography algorithms to allow for the assessment of connection probabilities in the human brain. Thereby, the local noise induced disturbance in the diffusion data is accumulated additively due to the incremental progression of streamline tractography algorithms. Graph based approaches have been proposed to overcome this drawback of streamline techniques. For this reason, the bootstrap method is in the present work incorporated into a graph setup to derive a new probabilistic fiber tractography method, called BootGraph. The acquired data set is thereby converted into a weighted, undirected graph by defining a vertex in each voxel and edges between adjacent vertices. By means of the cone of uncertainty, which is derived using the wild bootstrap, a weight is thereafter assigned to each edge. Two path finding algorithms are subsequently applied to derive connection probabilities. While the first algorithm is based on the shortest path approach, the second algorithm takes all existing paths between two vertices into consideration. Tracking results are compared to an established algorithm based on the bootstrap method in combination with streamline fiber tractography and to another graph based algorithm. The BootGraph shows a very good performance in crossing situations with respect to false negatives and permits incorporating additional constraints, such as a curvature threshold. By inheriting the advantages of the bootstrap method and graph theory, the BootGraph method provides a computationally efficient and flexible probabilistic tractography setup to compute connection probability maps and virtual fiber pathways without the drawbacks of streamline tractography algorithms or the assumption of a noise distribution. Moreover, the BootGraph can be applied to common DTI data sets without further modifications and shows a high repeatability. Thus, it is very well suited for longitudinal studies and meta-studies based on DTI.
- Published
- 2013
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.