The tag has no wiki summary.

learn more… | top users | synonyms

-3
votes
0answers
85 views

Is finding the longest cycle in a directed graph vs undirected graph NP hard? [closed]

To find the girth or the shortest cycle in a directed/undirected graph one can for edge edge, remove it from the graph and find the shortest distance between the end points. The shortest such distance ...
3
votes
0answers
88 views

For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?

In a related question, Saeed and Super8 have mentioned the Robertson-Seymour theory which enables us to find $k$ disjoint paths between pairs of vertices $\{s_i,t_i\}_{i=1}^k$ in poly time for fixed ...
0
votes
0answers
127 views

A* in triangulated search space

I have a question regarding the optimality of a specific A* in triangulated search spaces (planar). Suppose I have some convex polygon (the boundary) with some number of obstacles (other convex ...
3
votes
0answers
75 views

Multi-Agent Pathfinding

Quoting from Wang and Botea 2011: An instance is characterized by a graph representation of a map, and a non-empty collection of mobile units $U$. Units are homogeneous in speed and size. Each ...
8
votes
3answers
573 views

Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph

Quite similar to my previously posted question. This time however, the graph is undirected. Given An undirected graph $G$ with no multiple-edges or loops, A source vertex $s$, A target vertex $t$, ...
-5
votes
1answer
254 views

Self-avoiding walk in Graph [closed]

Short question: How many self-avoiding-filling-polygons are there in a grid-graph of $n×n$? Long question: Edit: This question is not about p = np. I am searching for a way to calculate the numbers ...
3
votes
1answer
173 views

Minimum offset while measuring TSP paths

I have Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I am trying to solve TSP with brute algorithm, and I want to ...
-2
votes
1answer
183 views

What's wrong with my linear programming formulation of longest path? [closed]

I have a directed graph which has cycles. Each edge has a positive weight. Now given two vertices $u$ and $v$, I want to find the longest simple path from $u$ to $v$. Simple means the path has no ...
2
votes
1answer
185 views

Shortest simple path with minimum edge cost minus node reward

I have a directed graph which has cycles. Each edge has a nonnegative weight and each vertex has a nonnegative reward. Given two vertices s and t, I need to find a simple path (a path with no ...
10
votes
2answers
312 views

Graph classes for which the diameter can be computed in linear time

Recall the diameter of a graph $G$ is the length of a longest shortest path in $G$. Given a graph, an obvious algorithm for computing $\text{diam}(G)$ solves the all-pairs shortest path problem (APSP) ...
4
votes
0answers
257 views

Path finding algorithm to maximise points of interest along the route

I am trying to write an algorithm to find a path (not the shortest one) between a given start and end point. An user will enter the start location, the end location and the available time to travel. ...
6
votes
1answer
177 views

Shortest paths perturbation

I have a graph $G=(V,E)$, with positive weights $w_e, e\in E$ on the edges, and I would like to randomly perturb the weights of the edges so that for each pair of distinct vertices $(u,v)$ such that ...
0
votes
1answer
209 views

directed or bidirected in relation to mssp (Multiple source shortest path)

Firstly I wanted to ask. If I have a undirected graph and split all the edges into two directed edges is it still called directed or does it become bi-directed? this is a picture of what I mean The ...
3
votes
1answer
702 views

Finding the shortest path in the presence of negative cycles

Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the ...
2
votes
0answers
203 views

Dynamic shortest path data structure for DAG

Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted. I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
3
votes
1answer
224 views

Breadth first search and Eppstein K shortest paths algorithm

I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf I have trouble particularly ...
3
votes
1answer
184 views

Dynamic all-pairs shortest paths - O(1) query

I'm trying to come up with an algorithm to solve all-pairs shortest paths (APSP) problem in dynamic directed planar graph with nonnegative real weights. Additionally: My primary focus is to achieve ...
1
vote
0answers
65 views

What are the differences between Theta* and Field D*?

Both Theta* and Field D* are variations on the A* algorithm, but are adapted for any-angle pathfinding rather than pathfinding constrained to a grid. The primary difference between these two ...
3
votes
2answers
656 views

Finding a minimum “node” weight path

Suppose a graph with node weights only (no edge weights). For a given source-sink pair, how can I find a path with the minimal sum of node weights? Does this problem have a name? Is it possible to ...
24
votes
0answers
828 views

Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?

Roughly speaking, my question is: How costly is to make a cyclic graph acyclic while preserving all simple $s$-$t$ paths? Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$. ...
8
votes
1answer
255 views

Motivation for Developing Shortest Path Simplex Algorithms

I'm reading Efficient Shortest Path Simplex Algorithms by Donald Goldfarb, Jianxiu Hao and Shen-Roan Kai who considered "the specialization of the primal simplex algorithm to the problem of finding a ...
0
votes
1answer
365 views

Implementing D* Lite for Path-Planning - How detect Edge Cost Change?

I currently try implementing the D* Lite Algorithm for path-planning (see also here) to get a grasp on it. I found two implementations on the web, both for C/C++, but somehow couldn't entirely follow ...
2
votes
0answers
316 views

A constrained shortest path problem. What is the complexity?

I've got the following problem: Consider a graph $G=(V,E)$ with $V=\{v_1,\ldots,v_n\}$, and edge-set $E=\{e_1,\ldots,e_m\}$, with associated costs $c_1,\ldots,c_m$. The problem is to find the ...
5
votes
2answers
702 views

In a resistor network, is there any relation between the shortest path and the maximum electric current path?

Consider a shortest path problem between the source $s$ and sink $t$ in an undirected weighted graph. There's a well known algorithm such as Dijkstra's algorithm that solves this problem. Naturally, ...
64
votes
6answers
23k views

How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?

A lot of pathfinding algorithms have been developed in recent years which can calculate the best path in response to graph changes much faster than A* - what are they, and how do they differ? Are ...
7
votes
3answers
336 views

Preprocessing Sparse, Directed Non-Planar Graphs for Faster Shortest Path

I'm trying to preprocess a very large and sparse directed graph in order to do faster shortest path searches. The vertices have no natural distance function, and the edges are unweighted. One ...
2
votes
1answer
234 views

Do you know a shortest path algorithm for weighted graphs with hard time windows on the edges and waiting allowed?

Title says it all. I have a weighted Graph G={V,E,ETW} where V is the node set, E the edge set and ETW is a set of edge time windows. A edge time window is a 3-Tuple (edge, starttime, endtime) with ...
1
vote
0answers
150 views

Dynamic k-shortest paths in a weighted transducer

I'm looking for references relating to dynamically computing the k-shortest output paths through a stochastic, acyclic, weighted transducer that is being constructed on-the-fly. In this scenario ...