1
$\begingroup$

If I have a graph $G$ and a subset $G'$, for all topological sorts $S$ over $G$, is there a topological sort over $G'$ that is a subset of $S$?

As a software optimization I want to pre-compute $S$ and then find the sort over $G'$ by copying all the elements of $S$ that are in $G'$ (maintaining their order, obviously).

  • 0
    What about the toposort induced on $G'$ y a toposort of $G$?2012-10-24
  • 0
    @Eitzen for a software optimisation. I can compute the sort of $G$ ahead of time, store it in an array, and then easily find the sort of $G'$ by iterating through the array and copying the elements that are in $G'$.2012-10-24
  • 1
    Why not? I mean, a topological sort is restricted by the edges present, removing these restrictions makes the original sort still valid.2012-10-24
  • 0
    @Hendrik: You could post that as an answer so that the question doesn't remain unanswered.2012-10-24
  • 0
    @joriki. Thanks for the hint. Frankly I was afraid I was overlooking some details and was drawing too fast a conclusion,2012-10-25

1 Answers 1