Skip to main content
Computer Science

Questions tagged [path]

Ask Question

The tag has no summary.

29 questions
Newest Active Bountied Unanswered
3 votes
1 answer
344 views

Given a directed unweighted graph and a set of nodes $N$, I have to find all the paths of length at most $L$ passing thru all the nodes. Since I am not enforcing each node to be visited only once, you ...
giz's user avatar
  • 31
0 votes
0 answers
81 views

I am looking at the language $F$ containing all $G,v_0,v_1$ s.t.: $G$ is undirected $G=(V,E)$ $v_0,v_1\in V$ $|V|=n$ There are $2^n$ paths between $v_0$ and $v_1$ I would like to prove that $F\notin ...
Benicio Agüero's user avatar
  • 142
1 vote
2 answers
169 views

I have a directed graph (DAG) containing many nodes, all with various attributes (node attributes not edge attributes). I have a single target (finish) node and a set of source (start) nodes. I want ...
laurence 's user avatar
  • 11
7 votes
3 answers
259 views

Given an undirected graph $G$ and two vertices $s$ and $t$, i want to find a minimum set of edges $E$ in $G$ such that every (simple) $s$-$t$-path contains at least 2 edges from $E$. Is this problem ...
tgnome's user avatar
  • 153
12 votes
1 answer
1k views

I am interested in the following algorithmic problem: Given a strongly connected directed graph $G$, I want a "short" (see below for what I mean by short) walk that starts with an arbitrary ...
Michal Dvořák's user avatar
  • 796
2 votes
0 answers
74 views

Given an undirected graph, two vertices $s$ and $t$, and two integers $k$ and $r$, then a $k$-set of internally disjoint $s$-$t$-paths is defined to be a set of exactly $k$ $s$-$t$-paths that share no ...
tgnome's user avatar
  • 153
6 votes
0 answers
199 views

Given an undirected graph, two vertices $s$ and $t$, and two integers $k$,$l$ - what is the complexity of finding $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are pairwise ...
tgnome's user avatar
  • 153
3 votes
1 answer
83 views

Say that I have a plasma gun: It's easy to compute the trajectory of the plasma ray starting from the gun. However, another ray may come from afar: As everybody knows, plasma rays are deviated when ...
cdupont's user avatar
  • 131
2 votes
0 answers
106 views

Assume I generate a random binary tree with a bounded height with $n$ nodes. For a given key we measure the length of its path (the maximum can be $n-1$). So my Question is what is the distribution of ...
Jungle's user avatar
  • 21
0 votes
1 answer
225 views

I hope this is the correct subpage of SE, if not please direct me to the more appropriate place. Imagine the following scenario: You are put into a random but known position inside a given maze. The ...
Plagiatus's user avatar
  • 101
1 vote
1 answer
186 views

I've read that the number of distinct paths in a graph can be exponential in relation to the number of vertices, later I encountered a problem which I spent some time trying to solve on my own. The ...
Aishgadol's user avatar
  • 377
2 votes
1 answer
112 views

I am using a Genetic Algorithm framework to solve a path-finding problem. Specifically, given the following 32x32 maze: ...
ex1led's user avatar
  • 121
3 votes
1 answer
364 views

Some time ago I had in one of the big tech interviews the following question that I still don't know how to approach it. You have a chains of reservations from AirBnb: ...
Andrei T's user avatar
  • 31
4 votes
1 answer
655 views

I encountered a problem, where I am given a (fully-connected) graph within a metric space, where each edge weight is either 1 or 2. My task is to prove that the following greedy algorithm gives a $\...
NiRvanA's user avatar
  • 159
0 votes
1 answer
41 views

Given the following problems: 2VertexDisjointPaths: Given: a directed Graph $G$ und vertices $s1, s2, t1, t2$. Question: Do paths $p1$ from $s1$ to $t1$ and $p2$ from $s2$ to $t2$ exist if $p1$ and $...
HelloCS's user avatar
  • 3

15 30 50 per page
1
2