日期: Fri, 28 Mar 2008 00:02:30 +0800
寄件人: Kun-Mao Chao
主旨: Union & Find
收件人: ACB

嗨！各位 ACB 夥伴：

有些問題，大家已經放手不管了三十年，居然還有人 能鑽研進去，並提出新看法，實在不可思議。

Union & Find這個教科書大家耳熟能詳的問題，以及Tarjan驚人的amortized分析，我們都已接受它的解法是 almost linear (related to a functional inverse of Ackermann's function)，沒想到前陣子居然有人 說這問題的解法根本就是 linear!請見：http://www.cs.uiowa.edu/~hzhang/union-find.pdf。

如果驗證屬實，那這可真是個大突破；如果驗證錯了， 我仍然要對作者能「從不疑處疑」的精神，致上最高 的敬意。(據說這論文送到STOC 2008，但並沒被接受，很有可能是錯了。)

確認屬實再update自己的認知，否則就當茶餘飯後的消遣吧。

坤茂

----- Original Message -----
From: Kun-Mao Chao
To: ACB
Sent: Friday, March 28, 2008 8:56 AM
Subject: Re: Union & Find

嗨！各位 ACB 夥伴：

每個人都曾有過「說曹操，曹操到」的經驗，天下事有時就是這麼湊巧！今天清晨我的「老生短訊」才提到演算法領域的神 Tarjan，沒想到剛剛我就收到 Tarjan團隊寄來的一篇論文初稿，除了引用效飛和我的論文外，也詢問我們的看法。效飛和我在一箭落地的時間內，就共同回覆了該信函，收件的三人中，也包括了 Bob Tarjan。效飛，謝謝你的佳作。

我只能說：神啊，真的很神！

坤茂