Tuesday, August 14, 2007

Graph minor and some results

如果一個圖 H 可以經由另一個圖 G 做出 vertex deletions,edge deletions 和/或 edge contractions 而得 (不計動作的順序),則我們稱 HG 的 minor。此外,任何圖皆為自己本身的一個 minor (i.e., 不做任何 taking minor 的動作)。

有三個定理如下:

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

Theorem:
For every graph H, there exists an 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).


印象中,minor 這傢伙還蠻常出現在 fixed-parameterized problems 裡頭的(??)值得注意一下。

3 comments:

BarrosH said...

Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring.
by Demaine ED, Hajiaghayi MT, Kawarabayashi KI

Joseph, Chuang-Chieh Lin said...

Thanks, BarrosH.

不過我文中提到的"與 fixed-parameter algorithms有關" 多少跟 problem kernels 搞混了。

但是還是非常有關就是了。

對了,你有這本的 eBook 嗎? XD

Joseph, Chuang-Chieh Lin said...

這是發表在 FOCS'05 的 paper。
(自己回應)