Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
schumitsch
on Sept 27, 2010
|
parent
|
context
|
favorite
| on:
First improvement of fundamental algorithm in 10 y...
I think the title is appropriate. The approximate solution is the interesting one, as the exact solution is believed to be intractable.
cdavidcash
on Sept 27, 2010
|
next
[–]
This is absolutely not true. The wikipedia page for the max flow problem lists several (slower) poly-time algorithms for solving exact max flow. Most theory-101 classes cover at least Ford-Fulkerson.
danger
on Sept 27, 2010
|
prev
[–]
I don't think that's true. See, for example, Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching (Karger-Levine, 1997):
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.3...
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
