5 results on '"Shortest path problem"'
Search Results
2. Simple paths with exact and forbidden lengths.
- Author
-
Dolgui, Alexandre, Kovalyov, Mikhail Y., and Quilliot, Alain
- Subjects
GRAPHIC methods ,GEOMETRIC vertices ,COMPUTATIONAL complexity ,GRAPH theory ,COMPUTER algorithms - Abstract
Abstract: We study new decision and optimization problems of finding a simple path between two given vertices in an arc weighted directed multigraph such that the path length is equal to a given number or it does not fall into the given forbidden intervals (gaps). A fairly complete computational complexity classification is provided and exact and approximation algorithms are suggested. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
3. 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
4. Dynamic optimization of the strength ratio during a terrestrial conflict
- Author
-
O. Hudry, G. Coppin, A. Sztykgold, Département Logique des Usages, Sciences sociales et Sciences de l'Information (LUSSI), Université européenne de Bretagne - European University of Brittany (UEB)-Télécom Bretagne-Institut Mines-Télécom [Paris] (IMT), Traitement Algorithmique et Matériel de la Communication, de l'Information et de la Connaissance (TAMCIC), Ecole Nationale Supérieure des Télécommunications de Bretagne-Centre National de la Recherche Scientifique (CNRS), Laboratoire Traitement et Communication de l'Information (LTCI), Télécom ParisTech-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), and Institut Mines-Télécom [Paris] (IMT)-Télécom Bretagne-Université européenne de Bretagne - European University of Brittany (UEB)
- Subjects
Mathematical optimization ,Computational complexity theory ,Computer science ,Process (engineering) ,Heuristic ,Decision theory ,Graph theory ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,010501 environmental sciences ,Dynamic programming ,01 natural sciences ,Computational complexity ,03 medical and health sciences ,0302 clinical medicine ,Shortest path problem ,030221 ophthalmology & optometry ,Game theory ,Decision making ,0105 earth and related environmental sciences - Abstract
International audience; The aim of this study is to assist a military decision maker during his decision-making process when applying tactics on the battlefield. For that, we have decided to model the conflict by a game, on which we will seek to find strategies guaranteeing to achieve given goals simultaneously defined in terms of attrition and tracking. The model relies multi-valued graphs, and leads us to solve a stochastic shortest path problem. The employed techniques refer to temporal differences methods but also use a heuristic qualification of system states to face algorithmic complexity issues
- Published
- 2007
5. Exact and Approximate Truthful Mechanisms for the Shortest-Paths Tree Problem
- Author
-
Luciano Gualà and Guido Proietti
- Subjects
General Computer Science ,Settore INF/01 - Informatica ,Applied Mathematics ,Mechanism design ,Graph theory ,Function (mathematics) ,Tree (graph theory) ,Upper and lower bounds ,Computer Science Applications ,Combinatorics ,Computational complexity ,Algorithmic game theory ,Algorithmics ,Shortest path problem ,Multiple edges ,Algorithmic mechanism design ,Mathematics - Abstract
Let a communication network be modeled by an undirected graph G=(V,E) of n nodes and m edges, and assume that edges are controlled by selfish agents. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most popular structures in communication networks, i.e., the single-source shortest paths tree. More precisely, we will study several realistic scenarios, in which each agent can own either a single or multiple edges of G. In particular, for the single-edge case, we will show that: (i) in the classic utilitarian case, the problem can be solved efficiently in O(mnlogα(m,n)) time, where ±(m,n) is the inverse of the Ackermanns function; (ii) in a meaningful non-utilitarian case, namely that in which agents valuation functions only depend on the edge lengths, the problem can be solved in O(m+nlogn) time. Conversely, for the multiple-edges case, we will show in the utilitarian case an O(mP+nPlogn) time truthful mechanism, where P=O(n) denotes the number of agents participating in the solution, while in the same non-utilitarian case we will prove a general lower bound to the approximation ratio that can be achieved by any truthful mechanism, by showing that no c-approximate mechanism can exist, for any fixed c < 5+√13 / 3+√13.
- Published
- 2007
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.