0
$\begingroup$

Essentially, it describes something like a neural network with adjacent layers being bipartite graphs. I am particularly interested in efficient algorithms to find some subset of vertices in layer 3 that are reachable through every edge from some input vertex in layer 1.

In my example graph, the first vertex in layer 3 satisfies this condition for every vertex in layer 1. The second vertex in layer 2 satisfies this condition for the second vertex in layer 1, but not the first and third vertices.

$\endgroup$
  • $\begingroup$ This is also just a bipartite graph $\endgroup$ – Morgan Rodgers Feb 4 '17 at 22:24
  • 2
    $\begingroup$ (all the even numbered layers together form one part, and the odd-numbered layers form a second part). Then only distinction is that you have partitioned the two parts of your bipartite graph into layers. $\endgroup$ – Morgan Rodgers Feb 5 '17 at 3:42
  • $\begingroup$ "...some subset of vertices in layer 3 that are reachable through every edge from some input vertex in layer 1." The bold part doesn't make sense to me since there are no edges from layer 1 to layer 3. Can you re-explain? $\endgroup$ – Casteels Feb 24 '17 at 19:22
  • $\begingroup$ Well, there are tripartite (and, more generally, multipartite) graphs. $\endgroup$ – Ivan Neretin Feb 24 '17 at 19:25
  • $\begingroup$ @Casteels I should probably have phrased it better. There doesn't need to be an edge directly from layer 1 to layer 3, just along the path. $\endgroup$ – forkexec Feb 25 '17 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.