Comments (7)
Link is dead, consider https://github.com/TimonKnigge/TCR/blob/master/snippets/flowalgorithms/dinic.cpp
from kactl.
I guess we can remove Hopcroft-Karp when we add Dinic, to win back space.
from kactl.
Do you also still need EdmondsKarp in this case? Otherwise, it would give PushRelabel, Dinic and EdmondsKarp as flow options. While the last two have the same complexity.
from kactl.
Possibly worth keeping if it's shorter? (Surely Dinic's must be faster than EdmondsKarp.) On the other hand, maybe we should just unify on a single flow algorithm, to avoid being able to pick the wrong thing. This part of KACTL has always been a mess...
from kactl.
EdmondsKarp is VE^2, while Dinic is EV^2. Dinic's also has a lot of nice properties on things like unit graphs or bipartite matching graphs too (VE^(1/2)
for bipartite matching graphs, and min(V^(1/2), E^(2/3))E
on unit graphs). So using Dinic's can also obsolete Hopcroft Karp too.
from kactl.
I think this issue, at least, is resolved. There's another discussion to be had about the "Flow algorithm" situation.
from kactl.
Yep.
from kactl.
Related Issues (20)
- In whole Geometry section, there are no epsilon. HOT 1
- Interpolation Template
- Add finite state automaton to KMP
- Add wavelet tree HOT 2
- Replace Manacher with Eertree?
- Add Half-plane intersection? HOT 2
- General Matching has unnecessary factor of 8
- Can we have Lyndon Factorization
- Faster hashmap
- Make string hashing ARM-friendly HOT 1
- Beginner-friendliness of Lazy Segment Tree
- Wrong Time Complexity for MinCostMaxFlow HOT 1
- dead link in mod mul
- Lazy segment tree is difficult to modify for other operations HOT 3
- Simplification of "rotate" implementation for splay HOT 1
- make euler walk return edge indexes by default HOT 1
- Factor.h can be hacked HOT 3
- Typedef is outdated
- outdated comment
- run tests with runtime debug flags HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from kactl.