New answers tagged

1

Answer to Question 1: Because of how we chose 𝑣, we know that the distance of vertex 𝑢 from the source 𝑠 did not decrease, i.e., 𝛿𝑓′(𝑠,𝑢)≥𝛿𝑓(𝑠,𝑢) Why the shortest-path from 𝑠 to 𝑢 after the augmentation of flow 𝑓 must be greater than or equal to the distance before the augmentation ? How it is possible to have greater distance that it ...


1

If I understand correctly you only have a problem when the graph $G = (V,E)$ of the vertex-cover instance has isolated vertices. In this case you can transform $G$ into a related graph $G' = (V \cup \{x,y \}, E')$ by adding a two new vertices $x$ and $y$ such that $x$ and $y$ are connected to each other by an edge, and there is an edge between $x$ and each ...


0

The correctness of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification, in this case, starting from the pre-condition $\alpha$ if the algorithm executes and land in states described by $\beta$ where the pre-condition is as weakest as possible and post-condition is as strongest as possible. The algorithm is ...


Top 50 recent answers are included