Abstrakt. Minsta nedskärningar har varit nära relaterade till kortaste vägar i planar grafer via planar dualitet - så länge graferna är oriktade. Även maximala flöden är nära relaterade till kortaste vägar av samma anledning - så länge källan och diskhon är på ett gemensamt ansikte. I detta dokument ger vi en överensstämmelse mellan maximala flöden och kortaste vägar via dualitet i riktade plandiagram utan begränsningar på källan och sjunka. Vi tror att detta är en lovande väg för att utveckla algoritmer som är mer praktiska än de nuvarande asymptotiskt bästa algoritmerna för maximalt st-flöde.
Borradaile och Harutyunyan REF utforskade detta sökväg-flöde dualitet ytterligare och visade en korrelation mellan maximala flöden och kortaste vägar i riktade planar grafer utan några begränsningar på platserna för källan och diskhon.
Maximum st-flow in directed planar graphs via shortest paths
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}