search

kalexmills / flownet

Flow network solver implemented in Go; handles max-flow and circulations with node and edge demands via a push-relabel algorithm.
MIT License
2 stars 1 forks source link

What algorithm do you use? #7

Closed skaurus closed 1 year ago

skaurus commented 1 year ago

Hey, I think it is worth documenting somewhere (maybe both in a source code and in a repo description) what algorithms do you use for solving these problems and what are their complexity.

Thanks for the project!

skaurus commented 1 year ago

I mean, there is lot of variations of push-relabel.

kalexmills commented 1 year ago

Good point -- it's been a minute since I did this project so I would definitely need to go back and review the implementation. IIRC they're straight-forward applications of techniques cobbled together from Wikipedia and Schrijver's book on Combinatorial Optimization.

skaurus commented 1 year ago

Yeah, a minute 😅 I was trying to get a sense of O-complexity of the used algorithm, but it looks like there is no ready answer. I'll close my issue then. Thanks!