Feasibility test

Creator

Creator

Seonglae Cho

Created

Created

2023 Nov 2 7:22

Editor

Editor

Seonglae Cho

Edited

Edited

2023 Nov 2 7:29

Refs

Refs

notion image

Contradiction of with satisfiable program with negative-weight cycle

Contradiction of with satisfiable program with negative-weight cycle

By

Bellman-Ford algorithm, we can report constraint graph has negative-weight cycle or not.

append virtual edge to all vertex

notion image

notion image

Recommendations

////////