See More
Popular Forum

MBA (4887) B.Tech (1769) Engineering (1486) Class 12 (1030) Study Abroad (1004) Computer Science and Engineering (988) Business Management Studies (865) BBA (846) Diploma (746) CAT (651) B.Com (648) B.Sc (643) JEE Mains (618) Mechanical Engineering (574) Exam (525) India (462) Career (452) All Time Q&A (439) Mass Communication (427) BCA (417) Science (384) Computers & IT (Non-Engg) (383) Medicine & Health Sciences (381) Hotel Management (373) Civil Engineering (353) MCA (349) Tuteehub Top Questions (348) Distance (340) Colleges in India (334)
See More

Most efficient way to recompute flow in a graph after changing capacity of one edge

Course Queries Syllabus Queries

Max. 2000 characters



( 4 months ago )

What is the most efficient way to recompute maximum flow in a graph when:

  • we increase flow on one edge by one
  • we decrease flow on one edge by one

In the first case, is is enough to run one iteration of Ford-Fulkerson algorithm? In the second case, we need to recompute maximum flow only if the edge is part of a set of edges of maximum flow. Is it also enough to run one iteration of Ford-Fulkerson?

what's your interest