在 2000s 年的 partitions 問題，關心的是 XML tree 上的儲存， 而 1970s 上的 partitions 則是關注於 Programs 的儲存。
在眾多 Reference 中，撇見一篇 1971 JACM 的 Optimal Sequential Partitions of Graphs， 腦中還在想這麼老舊的文章是否有研讀的必要。
看在其為 JACM 的份上，便在 Google Scholar 輸入關鍵字，出現 82 篇引用，以 JACM 的文章這種引用數或許不算多。
但或許是標題已標明了 "optimal" 一詞 ，後續也不太有改進的空間。
DBLP 內雖只有 28 筆資料，但在 google 輸入 Brian W. Kernighan ，第一筆不是作者的個人網頁，而是 wikipedia 頁面，而下方的圖片搜尋，還出現一個熟悉的照片。
這個蓋著 ANSI C 的印章的書，不就是我五年前修習單維章教授所開設程式設計的教科書，我的 C 語言啓蒙書。這...這就是傳說中的C語言經典 K & R 。原來 Kernighan 就是其中的 K。
很快速地翻閱了這篇僅有 7 頁的 Optimal Sequential Partitions of Graphs, 整篇也只是用到了 Dynamic Programming 並沒有用到太複雜的概念。我當初還在想是不是因為 Kernighan 的名氣讓這篇被接受。
查完 DBLP 資料，竟發現這篇 “Optimal Sequential Partitions of Graphs” 是 Kernighan 在 DBLP 的第一筆資料。細查其他文獻，看到 1969 年有篇 Ph.D Thesis 其作者就是 Kernighan ，也就是這篇 JACM 的文章其實就是 Kernighan 博士論文的一個結果。所以拿 Partition Problem 來當 Ph. D Thesis 或許是件很值得驕傲的事吧。
我以下圖，來解釋 Kernighan 在這篇考慮的 partition 。因其考慮的是 programs 的 partitioning, 因此 graphs 的每個 vertices 有其自然的順序，在 partition 時，每個 partition 只能包含一段連續的 vertices 。而其邊上的 weight 表示這兩個 vertices 會相互呼叫的頻率。因此每個 partitions 給定其大小上限(下列為 4)，要找一個切割方式，使得那些跨 partitions 的 edges 之 weight 總和越小越好。
在上述的圖示中，可窺探其實只用到了 Dynamic Programming 的概念，而在 Theorem 4 證其 running time 也只是 O(E) 。在這篇中，除了 Theorem1 證明了這是 optimal 的解外，他也論證 (Theorem 2) 此方法會得到在所有 optimal solutions 中， partitions 的個數是最小的。在 Theorem 3 論證了 partitions 的個數也不會太大( expansion factor <2)。最特別的是其 Theorem 5 的敘述，不可能存在一個方法，只靠 local information 就能決定 cut edge 要在哪邊。
整體來看，這篇文章論述是很完整，但手法概念上其實不算難懂，能上 JACM 或許是這問題在當時有其重要性？
