I'm studying for a final and when looking for the shortest path in a graph from one vertex to another, what is meant by k-skips?

One website defines it as the ability to change the weight of one edge to zero, as if you don't include it in the path distance.

Another one defines it as:

$P*$ is a k-skip shortest path from s to t, if it includes at least a vertex out of every k consecutive vertices in P

Which I can't seem to understand. I would appreciate some clarification in the matter.


The second definition that you quote is informal, and open to interpretation. Fortunately, the same paper On $k$-skip shortest paths by Tao, Sheng and Pei contains a formal definition, Definition 2 on page 4.

That said, $k$-skip is not a common term, and doesn't really have a universally accepted definition (or indeed, any universally known definition), except perhaps in work following up on the Tao et al. paper mentioned above.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.