Blogs about: 圖論 Graph Theory
酷網誌
All pairs Minimum Cuts in O(V^3)?
最近在研究 Gomory-HU Tree ，以及 Stoer-Wagner Algorithm 提出的 Maximum Adjacency Search 特性。我想說不定此兩概念可結合，便能以 O(V^3) 求出無向圖所有的最小割？畢竟最短路徑樹可以費時 O(V^3) 算得，最小生成樹可以費時 O(V^3) 算得，所以最小割樹或許也能費時 O(V^3) 算得。… 更多 →
DJWS的網路日誌 - 最新消息
All pairs Minimum Cuts in O(V^3)?
DJWS wrote 5 days ago: 最近在研究 Gomory-HU Tree ，以及 Stoer-Wagner Algorithm 提出的 Maximum Adjacency Search 特性。我想說不定此兩概念可結合，便能以 O(V … more →
Maximum Weight Bipartite Perfect Matching: Hungarian Algorithm
DJWS wrote 3 weeks ago: http://www.csie.ntnu.edu.tw/~u91029/Matching.html … more →
Maximum Cardinality Matching: Blossom Shrinking Algorithm
DJWS wrote 1 month ago: http://www.csie.ntnu.edu.tw/~u91029/Matching.html 感謝網友FRAXIS的協助。 … more →
Maximum Cardinality Bipartite Matching: Hopcroft-Karp Algorithm
DJWS wrote 1 month ago: http://www.csie.ntnu.edu.tw/~u91029/Matching.html 沒啥內容。看看就好。 … more →
Max-Flow: Preflow-Push-Relabel Algorithm再進化
DJWS wrote 3 months ago: http://www.csie.ntnu.edu.tw/~u91029/Flow.html 此次增加了Relabel-to-front Algorithm、Goldberg-Tarjan Algori … more →
Matching之課程投影片
DJWS wrote 8 months ago: http://www.arl.wustl.edu/~jst/cse/542/lec/chap10.ppt 課程投影片，內有O(V*E*alpha(E,V))最大匹配、O(V*E*log(V))最大權重 … more →
Max-Flow: Preflow-Push-Relabel Algorithm
— 2 comments
DJWS wrote 1 year ago: http://www.csie.ntnu.edu.tw/~u91029/Flow.html 前所未見的繁複演算法。我想以後很難再有比這個還難的了。 … more →
勘誤：Topological Sort
DJWS wrote 1 year ago: 今天發現我把 Dijkstra’s Algorithm（以及相關的演算法） 和 Topological Sort 的時間複雜度搞混了。錯的非常離譜。特此聲明。 年紀大了，腦袋就不太靈光了。 … more →
Stoer-Wagner Min-Cut Algorithm討論
— 1 comment
DJWS wrote 1 year ago: http://www.cs.dartmouth.edu/~rahul/Teaching/stoerwagner-mincut.pdf 各位好，最近我正在準備這個演算法的中文教學文件，不過我無法理解這個 … more →
Have your say. Start a blog.
See our free features →
On WordPress.com
