Skip to main content
added 196 characters in body
Source Link

Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique identifier.

Let's
Let's say I then have an input cycle, $c$ which is just a list of weightsthree edges (e.g $c=[10, 13, 26]$$c=[4,7,6]$).
  Does an algorithm exist that lets me search $G$ for the cycleinstances of $c$, and returns the identifiers of the matching nodes?
The cycles it returns must be closed loops, such as $[A, D, B, \text{(then back to A)}]$, rather than $[D, A, B, A]$

Here is a poorly-drawn example: A poorly-drawn example.

Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique identifier.

Let's say I then have an input cycle, $c$ which is just a list of weights (e.g $c=[10, 13, 26]$).
  Does an algorithm exist that lets me search $G$ for the cycle $c$, and returns the identifiers of the matching nodes?

Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique identifier.
Let's say I then have an input, $c$ of three edges (e.g $c=[4,7,6]$). Does an algorithm exist that lets me search $G$ for instances of $c$, and returns the identifiers of the matching nodes?
The cycles it returns must be closed loops, such as $[A, D, B, \text{(then back to A)}]$, rather than $[D, A, B, A]$

Here is a poorly-drawn example: A poorly-drawn example.

Added tags
Link
gmvh
  • 3.8k
  • 6
  • 33
  • 54
edited tags
Link
RobPratt
  • 5.8k
  • 1
  • 16
  • 27
Source Link
Loading