## Monday, August 20, 2007

### Research notes

6 個 taxa involves 5 quintet，所以可以先 fix 一個 quintet，再思考第 6 個 taxon 插入的情形嗎？這是一個方向。

### Plane on fire at Japanese airport - by BBC news

http://news.bbc.co.uk/2/hi/asia-pacific/6954397.stm

=======================================================

A Taiwanese China Airlines plane has caught fire at an airport on the southern Japanese island of Okinawa.

TV pictures showed the Boeing 737 passenger plane on the tarmac with huge flames and smoke billowing from it, as firefighters doused the fuselage.

A Japanese transport ministry official said all the passengers had left the aircraft before the fire started. There were also no crew members on board.

The plane had flown in from Taipei with more than 150 passengers on board.

=======================================================

## Sunday, August 19, 2007

### The first Valentine's Day since the marriage

Happy Chinese Valentine's Day, my dear wife. Thank God for bringing you to me.

## Wednesday, August 15, 2007

### After meeting with boss today

• 學著規劃好時間。與妻子 (家庭) 的相處時間短但品質要好。
• 目前我吸收學問的訓練夠了，但是我的解決問題的能力非常不足。
• 想解決問題的辦法前，先想想「該想什麼」、「目的為何」，不是茫茫然亂想。
• 多去 conjecture，然後加以證明之。
• Survey 文獻的速度要快！
• 想辦法讓每天都能有所進展。

1. 對於 NP-C 的 graph decision problems 而言，survey 其對應的 graph modification problems 與 property testing problems。
2. 觀察 quintet、 quartet topologies、 consistent trees 的「結構」。
3. consistent 的 trees 數量佔所有可能的 topology sets 的比例非常之小。
4. 對於一個 quintet，光看其中 induced 的 3 個 topologies 就可以知道這個 quintet 是否 consistent？
5. 當存在一個 quartet error 不在任何一個 local conflict (consistent quintet) 裡面時，又是怎樣的情形？
6. 與志仁討論或想辦法弄清楚 branch factors。

## Tuesday, August 14, 2007

### Graph minor and some results

Theorem: (Wagner's conjecture)
For every class of graphs $\cal{G}$, that is closed under taking of minors, there exists a finite set of graphs, ob($\cal{G}$), called the obstruction set of $\cal{G}$, such that for each graph G, $G\in \cal{G}$ if and only if there is no $H\in ob(\cal{G})$ that is a minor of $\cal{G}.$

Theorem:
For every graph H, there exists an $O(n^3)$ time algorithm, that, given a graph G, tests whether H is a minor of G.

Theorem:
For every planar graph H, there exists a constant c(H), such that for every graph G, if H is not a minor of G, then the treewidth of G is at most c(H).

### Studying treewidth of a graph

A tree-decomposition of a graph G = (V, E) is a pair $(\{X_i\mid i\in I\}, T = (I, F))$ with $\{X_i \mid i\in I\}$ a family of subsets of V, one for each node of T, and T is a tree such that

• $\bigcup_{i\in I} X_i = V.$

• for all edges $(v, w)\in E$ , there exists an $i\in I$ with $v\in X_i$ and $w\in X_i$.
• for all $i, j, k\in I$, if j is on the path from i to k in T, then $X_i\cap X_k\subseteq X_j.$
• The treewidth of a tree-decomposition $(\{X_i\mid i\in I\}, T = (I, F))$ is $\mbox{max}_{i\in I}|X_i|-1.$ The treewidth of a graph G is the minimum treewidth over all possible tree-decompositions of G.

====================================================

感覺上，treewidth 好像是一個圖 G 中 最大 clique 之 size 減 1，不知道有沒有反例。另外，clique tree 是 tree-decomposition 的特例，只是多了一條限制：tree 上的每個 node 都是原圖 G 上的 maximal clique。

如果一個圖的 treewidth 為 bounded，那麼很多原本是 intractable 的 graph problems，就可以在 polynomial time (甚至很多可以在 linear time) 被解掉。譬如： Independent Set Problem, Hamiltonian Circuit Problem, Steiner tree problem 等等。

在 R. Niedermeier 的 Invitation to Fixed-Parameter Algorithms 一書中提到底下事實：
For constant k, there is a famous resulting giving a linear-time algorithm to compute whether a graph has treewidth at most k. More precisely, the algorithm has running time $2^{\Theta(k^3)}\cdot k^{O(1)} \cdot n.$
此外，給定一個 parameter k 與一個圖 G 當作 input，"決定 G 的 treewidth 是否至多為 k " 的問題已被證明為 NP-C [cite: ACP87]。但是，對於任一固定的 k，這問題存在一個 O(nlog n) 的演算法 [cite: R92]。

[ACP87] S. Arnborg, D. G. Corneil, and A. Proskurowski: Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Math., Vol. 8 (1987), pp. 277-284.
[R92] B. Reed: Finding approximate separators and computing treewidth quickly. STOC'92, pp. 221-228.

## Sunday, August 12, 2007

不錯的免費古典音樂廣播，可以在唸書或思考問題時當背景音樂聆聽。

奇美古典音樂網 (無廣告播放古典小品音樂)

最近真想說：有奇美真好。
• ViewSonic LCD 由奇美代工；
• 奇美咖啡館的奇美冰咖啡超好喝；
• 奇美古典音樂網提供了以往中廣音樂網的古典音樂*。

* 註： 台北愛樂電台也不錯

## Wednesday, August 08, 2007

### Unlimited for giving comments at this blog now (回應不設會員的限制囉)

其實在看 BarrosH 的 blog 時，我早該發現的。過去我怕廣告以及一些類似垃圾信的東西佔據我的 blog comments，但是現在有字詞驗證的工具，所以也就沒必要限制發言者的身份了。

這兩天下來，我的個人網頁的訪客數比起我的 blog 所吸引的訪客數少很多很多，不過這才像話嘛！之前我寫的計數器簡直是垃圾，現在使用了 counterservis 提供的免費計數器之後，才反映出真正的訪客人數，而且還能加以分析訪客的來源、所使用瀏覽器以及查詢哪些網頁連結至我的網頁或 blog，似乎還蠻有趣的。

BTW，我老婆質疑我現在所舉辦的投票意義何在。其實，那只是拿來自爽用的。因為我發現 blogger 現在有提供投票的新功能，覺得好玩所以辦一個試看看。如果有什麼有趣的議題，我會再拿出來讓大家一起參與。

## Thursday, August 02, 2007

### Research notes (2 Aug, 2007)

$(2n + 1)!! = \frac{(2n+1)!}{2^n\cdot n!} = 2^{-n}\cdot P_{n+1}^{2n+1}.$

Then we have,

$(2n+1)!! \leq 2^{-n}\cdot (2n+1)\cdot (2n)^{n} = O(n^{n+1}).$

Therefore,

$(2n-5)!! = O((n-3)^{n-2}) = O(n^{n-2}).$

Note: When n is an odd integer, n!! = n * (n-2) * (n-4) * ... * 3 * 1

## Wednesday, August 01, 2007

### Being husband and a wife now...

感覺上，結了婚覺得沒差別就是有差別。也許就像某一本書上講的，結了婚以後，女孩要變成女人很快，可是男孩要成長為男人卻相對慢很多。我一直認為婚前婚後我會「始終如一」，這樣子的「沒差別」卻是跟我的另一半有著「大大的差別」。

結了婚以後，大家都是親人了，所以很多事情上的處理態度應該要有所轉變，可是我常停留在婚前那一套，所以常常使馬尾傻眼。因此，我覺得她對我的要求變多了，實際上，是我應該再成熟一點。總之，不能夠以「這是男人的通病」來混過去。我必須在態度和思維上有一些轉變。

不過還好結婚了，看了很多情侶交往過久最終仍分道揚鑣的悲慘故事，深深覺得自己很走運，早早把馬尾給定下來了。而從結婚前到現在發生了很多好事，我想我更要深深地感謝上帝的帶領，這當中真的有許多說不出的奇妙。

接下來的工作，就是讓彼此更加幸福而已。