84:
74:
53:
22:
379:
I agree, it's not nice to discuss his ethnicity in this article. But the fact that the algorithm was invented in the USSR and not in the West looks to me historically significant and it should be somehow mentioned in the article, perhaps at least by mentioning the journal in which the algorithm was
162:
This article uses the name "Yefim (Chaim) A. Dinitz", but I can't find any reference for the alternate name "Chaim", and I don't see it in the
Russian version of the article. (There's no linked Hebrew version of the article at the moment. The source cited is just a translation of the original paper
514:
I don't understand how the
Example ("simulation") is constructed starting the very first step, the initial "guess"(?) G_L in row "1." of the table. Why is there no flow from node (1) to node (2), but maximum flow of 4 from (1) to (3)? I understand that from (s) I can send 10 units to (1). I could
359:
I suggest that the segment in the first paragraph that refers to Dinitz as formerly Soviet be removed from the article. Also, consider changing
Israeli to Jewish or removing the reference to his ethnic background altogether. Finally a link to his personal homepage may be in order (see here:
331:
Do we have any evidence to believe that he had renounced his
Russian citizenship? If not, should we state that he is "former Russian"? Unless we are talking about ethnicity, in which case, he should have always been Jewish, and not either Israeli or Russian... just a thought ...
219:
Well he explains it right there in his article. Shimon Even first popularized the algorithm in the west under the name "Dinic'c algorithm", which was "rendered incorrectly as instead of ". That explains why alternative spellings of Dinitz's name are so rarely seen. --
423:
I don't see how it could possibly suggest that. It says that there are at most n-1 = O(V) blocking flows to be found and finding each one takes O(VE) time. Multiplying these quantities you get O(V^2 E). --
140:
444:
where did you get the inputs used in every path...? i'am applying this algorithm with my case study.and my problem is that i don't know where will i derived the inputs? please help me...
384:". As for a link to personal homepage - there's already a direct link to the paper about the algorithm on his website. That's sufficient. Another link to his homepage would be against
186:
Why is the
Algorithm called Dinic's algorithm, when the guy who invented it is called Yefim Dinitz? That doesn't make sense to me - I think it should be both written the same.
515:
also send 10 units to (2), but since this isn't done, I assume that we go on (in "depth first" mode) with outgoing arrows from node (1) and don't consider the edge (s)--: -->
310:
274:
408:
I might be missing something, but it seems as if the running time should be O(VE^2) rather than O(V^2E)? That's what the information in the
Analysis seems to suggest.
566:
130:
561:
535:
of the edges, then one should first have a flow of 8 units to node (4), next a flow of the remaining 2 units to node (3), and nothing to node (2).
164:
106:
496:
167:, I'll change the name to "Yefim Dinitz" tomorrow if we don't have a source by then. If you find a source later, please change it back! —
451:
409:
365:
313:
205:
348:
97:
58:
528:
nodes, then one should first have a flow of 2 units to node (2), then 4 units to node (3), and the remaining 4 units to node (4).
33:
276:
time using the
Malhotra-Kumar-Maheshwari blocking flow (MPM) algorithm? This would yield an overall running time of
500:
21:
413:
369:
317:
209:
455:
344:
39:
191:
163:
on the algorithm, which names the author as "E. A. Dinic".) Since sourcing is especially important for
83:
447:
381:
336:
172:
187:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
89:
73:
52:
279:
243:
340:
168:
385:
555:
544:
429:
393:
225:
484:
remains a bit cryptic in the definition. Unless, of course, it should be read as
102:
547:
504:
459:
433:
417:
397:
373:
352:
321:
229:
213:
195:
176:
79:
540:
425:
389:
221:
361:
201:
539:
So, how is the initial guess constructed? Thank you in advance! —
520:
the incoming 10 units are distributed over the outgoing arrows...
473:
A blocking flow is an s-t flow f such that the graph G' contains
480:
It would be useful to show G' in the example too, otherwise the
240:
Isn't it possible to find a blocking flow in a level graph in
15:
204:
He refers to his own work as Dinic's
Algorithm. Strange.
282:
246:
101:, a collaborative effort to improve the coverage of
470:The current text reads like this (emphasis mine):
304:
268:
8:
19:
47:
293:
281:
257:
245:
236:Complexity of blocking flow calculation
200:Look up his personal homepage on BGU -
49:
7:
526:in order of the label of destination
95:This article is within the scope of
38:It is of interest to the following
14:
567:Low-priority mathematics articles
115:Knowledge:WikiProject Mathematics
562:Start-Class mathematics articles
362:http://www.cs.bgu.ac.il/~dinitz/
202:http://www.cs.bgu.ac.il/~dinitz/
118:Template:WikiProject Mathematics
82:
72:
51:
20:
135:This article has been rated as
299:
286:
263:
250:
1:
353:17:43, 13 December 2010 (UTC)
177:21:31, 22 December 2023 (UTC)
109:and see a list of open tasks.
505:08:06, 12 January 2018 (UTC)
466:Definition of blocking flow?
434:19:11, 6 December 2011 (UTC)
418:04:08, 6 December 2011 (UTC)
322:20:20, 7 December 2009 (UTC)
196:09:17, 2 November 2009 (UTC)
460:10:37, 6 January 2012 (UTC)
583:
548:21:52, 22 April 2022 (UTC)
158:Source for alt name Chaim?
165:facts about living people
134:
67:
46:
516:(2) for the moment. But
380:originally published - "
305:{\displaystyle O(V^{3})}
269:{\displaystyle O(V^{2})}
141:project's priority scale
398:16:39, 6 May 2011 (UTC)
374:14:03, 6 May 2011 (UTC)
230:16:55, 6 May 2011 (UTC)
214:14:01, 6 May 2011 (UTC)
98:WikiProject Mathematics
388:(items 13 and 19). --
306:
270:
28:This article is rated
307:
271:
533:in order of capacity
382:Soviet Math. Doklady
280:
244:
121:mathematics articles
302:
266:
90:Mathematics portal
34:content assessment
450:comment added by
356:
339:comment added by
155:
154:
151:
150:
147:
146:
574:
462:
355:
333:
311:
309:
308:
303:
298:
297:
275:
273:
272:
267:
262:
261:
182:Dinic or Dinitz?
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
582:
581:
577:
576:
575:
573:
572:
571:
552:
551:
512:
510:Example unclear
497:213.203.132.119
478:
468:
445:
442:
406:
334:
329:
327:Former Russian?
289:
278:
277:
253:
242:
241:
238:
184:
160:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
580:
578:
570:
569:
564:
554:
553:
537:
536:
529:
511:
508:
472:
467:
464:
441:
438:
437:
436:
405:
402:
401:
400:
328:
325:
301:
296:
292:
288:
285:
265:
260:
256:
252:
249:
237:
234:
233:
232:
183:
180:
159:
156:
153:
152:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
579:
568:
565:
563:
560:
559:
557:
550:
549:
546:
542:
534:
530:
527:
523:
522:
521:
519:
509:
507:
506:
502:
498:
493:
491:
487:
483:
476:
471:
465:
463:
461:
457:
453:
452:122.52.159.76
449:
439:
435:
431:
427:
422:
421:
420:
419:
415:
411:
410:18.111.103.83
403:
399:
395:
391:
387:
383:
378:
377:
376:
375:
371:
367:
366:79.176.200.40
363:
357:
354:
350:
346:
342:
338:
326:
324:
323:
319:
315:
314:82.130.21.149
294:
290:
283:
258:
254:
247:
235:
231:
227:
223:
218:
217:
216:
215:
211:
207:
206:79.176.200.40
203:
198:
197:
193:
189:
181:
179:
178:
174:
170:
166:
157:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
538:
532:
525:
517:
513:
494:
489:
485:
481:
479:
474:
469:
446:— Preceding
443:
407:
404:Running Time
358:
335:— Preceding
330:
239:
199:
185:
161:
137:Low-priority
136:
96:
62:Low‑priority
40:WikiProjects
341:Gabiteodoru
112:Mathematics
103:mathematics
59:Mathematics
30:Start-class
556:Categories
477:s-t path.
386:guidelines
169:Vectornaut
448:unsigned
349:contribs
337:unsigned
188:Wadi oo
139:on the
440:inputs
36:scale.
545:Talk
531:...
524:...
501:talk
456:talk
430:talk
414:talk
394:talk
370:talk
345:talk
318:talk
226:talk
210:talk
192:talk
173:talk
541:MFH
490:one
488:or
426:X7q
390:X7q
364:).
222:X7q
131:Low
558::
518:if
503:)
495:--
492:.
486:an
482:no
475:no
458:)
432:)
416:)
396:)
372:)
351:)
347:•
320:)
312:.
228:)
212:)
194:)
175:)
543::
499:(
454:(
428:(
412:(
392:(
368:(
343:(
316:(
300:)
295:3
291:V
287:(
284:O
264:)
259:2
255:V
251:(
248:O
224:(
208:(
190:(
171:(
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.