1
$\begingroup$

Assume we have weighted DAG (directed-acycle-graph), source s and target t.

Define the number of edges as $E$.

Given $0<\alpha<1$:

Choose $\alpha*E$ edges to cut their weight by half so that the longest path from s to t is minimized.

Personal note: We've been asked this question by our professor. I assume the problem is NP-Hard. We are looking for some heuristics that will gives us good results, not necessarily optimal.

Any suggestions will be welcome.

Improve this question
$\endgroup$
3
  • $\begingroup$ (Seems to "prefer" paths with not much more than $\alpha\times E$ costly edges.) $\endgroup$
    – greybeard
    Jun 8, 2021 at 21:53
  • $\begingroup$ What do you meet by that @greybeard? You have no control over the initial longest-paths $\endgroup$
    – Amran Tomer
    Jun 8, 2021 at 22:17
  • $\begingroup$ It's just a musing about what difference $\alpha$ makes. Between paths with less than $\alpha\times E$ edges with weight>0: none. Path with most costly $\alpha\times E$ edges contributing less than half the cost: cost after halving greater than three quarters of the original. $\endgroup$
    – greybeard
    Jun 8, 2021 at 22:29

0

Reset to default

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.