Questions tagged [path]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
22 views

Point Cloud Complete 3D Area Coverage Path Finding Algorithm

So I have a point cloud, of a 3D object, as an input which I received from a 3D scanner. I would like to generate a path which covers the entire object, meaning I would like to come up with a complete ...
69 views

Find most vertices in a directed tree where no path of length less than 3 connects any pair

Given a directed tree $T = (V, E)$, we need to find a set of vertices $A \subseteq V$ such that for every two vertices $v,u \in A$ either there is no path between them or the path between them is of ...
49 views

How to find lightest path in directed weighted graph where each edge has a color

We're Given a directed graph $G = (V, E)$ and a weight function $\omega : E \rightarrow \mathbb{Z}$. Each edge is colored with one of these colors: Red, Green, Blue. Given two vertices $s,t \in V$, ...
70 views

Finding optimal path for a reproduction problem

Given a finite set of lists with elements ($e_1, e_2,..., e_7$) and $e_i = True, False$. It is possible to create a new list by taking two lists and apply the $\land$ operator on both lists ($e_i$ in ...
11 views

What are the possible algorithms behind dex aggregators?

I want to know what is the algorithm behind 1inch, paraswap, and other dex aggregators. The problem is: Imagine you want to sell a huge amount of some coin and a there are multiple brokers with ...
25 views

Given an unweighted graph $G$, the problem is to add links to the graph with total minimum cost such that the diameter of the graph becomes at most a constant $k$? The cost of adding a link $(u,v)$ is ...
32 views

Find the k length path that maximize a node associate metric

Let's say I have : a Graph g v vertices. Each vertex is associated to a cost c. A special vertex called the starter vertex or vs. I want to find the path p of length 10 (for example), that start ...
126 views

Find every edge for which every s,t-path in a DAG goes through that edge

Given a connected sourced/sinked directed acylic graph $G = (V, E \subseteq V^2, s \in V, t \in V)$, we want to enumerate the edges $e \in \mathsf{Bottleneck}(G) \subseteq E$ for which every $s$,$t$-...
26 views

...
46 views

Reducing infinite paths of a transition system to its set of sets of states

Consider a transition system defined by $\langle S,T \rangle$, where $S$ is a set of states and $T \subseteq S \times S$ is a set of transitions, where $T$ is total, i.e. for every state $s$ there is ...
159 views

Longest path in a strongly connected component

So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component. My idea is: In a strongly connected component ...
Determine if there's a $P_3$ as an induced subgraph in a graph $G$
Given a graph $G$ on $n$ vertices with $m$ edges, show an algorithm that determines if there's a $P_3$ as an induced subgraph in $G$ in $O(m+n)$ time. ($P_3$ is the path on 3 vertices). What I was ...