You are not logged in. Please login at www.codechef.com to post your questions!

×

What is level graph and Blocking flow in Dinic's maxflow algorithm?

I am learning Dinic algorithm from max-flow here.I am not able to understand the terms Level graph and blocking flow any one help me.

asked 22 Sep '15, 06:57

pallesai's gravatar image

4★pallesai
176831
accept rate: 17%


level graph means u r simply making a rooted tree where every node is at a shortest distance from root. also the sink is at a shortest possible level from the src.

blocking flow means after u convert the residual graph into a level graph u pass maximum flow through the level graph and when it becomes impossible to send any flow further for the current level graph.

then again u make another possible level graph

i learned it recently and solved few problem with it.

link

answered 25 May '16, 22:42

farhad519's gravatar image

0★farhad519
1
accept rate: 0%

@farhad519

provide the link to problems and some good resources to learn it.

(26 May '16, 07:44) arpit7281★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×114

question asked: 22 Sep '15, 06:57

question was seen: 2,699 times

last updated: 26 May '16, 07:44