一些探測圖類別之辨識演算法設計

Recognition Algorithms for Some Probe Graph Classes

洪綾珠(Ling-Ju Hung)

指導教授 ： 羅曼斯 ； 張貿翔 ； 吳邦一

國立中正大學/工學院/資訊工程學系/博士(2012年)

摘要

令$mathcal{G}$表示一個圖類別,無向圖$G$是一個探測$mathcal{G}$圖(probe $mathcal{G}$ graph),假如
我們可以在$G$中找到一個Independent Set並且在這個Independent Set中加邊,使得加完邊後的圖是一個$mathcal{G}$圖類別中的圖,
根據定義,圖類別$mathcal{G}$是探測圖類別$mathcal{G}$的一個子類別。給定一圖$G$，假如$G$中的任兩點在任何連通的導出子圖(induced sugraph)的距離和在$G$中的距離相同,
我們稱$G$為保距圖 (distance-hereditary graph),二分保距圖(bipartite distance-hereditary graph)既是保距圖也是二分圖(bipartite graph),托勒密圖(ptolemaic graph)是
弦圖(chordal graph)的子圖類別滿足圖中不含有導出子圖為gem的圖,二分保距圖和托勒密圖都是保距圖的子圖類別,在本篇論文中,我們設計了三個時間複雜度為 $O(nm)$ 的辨識演算法,
用來辨識保距圖的探測圖 (probe distance-hereditary graphs),二分保距圖的探測圖 (probe bipartite distance-hereditary graphs),托勒密圖的探測圖 (probe ptolemaic graphs)。

關鍵字

二分保距圖 ； 保距圖 ； 探測圖 ； 托勒密圖

並列摘要

Let $mathcal{G}$ denote a graph class. An undirected graph $G$ is
called a {em probe $mathcal{G}$ graph} if one can make $G$ a graph
in $mathcal{G}$ by adding edges between vertices in some
independent set of $G$. By definition graph class $mathcal{G}$ is a
subclass of probe $mathcal{G}$ graphs. A graph is {em distance
hereditary} if the distance between any two vertices remains the
same in every connected induced subgraph. {em Bipartite
distance-hereditary graphs} are both bipartite and distance
hereditary. {it Ptolemaic graphs} are chordal and induced gem free.
Both bipartite distance-hereditary graphs and ptolemaic graphs are
subclasses of distance-hereditary graphs. In this dissertation, we
propose $O(nm)$-time algorithms to recognize probe
distance-hereditary graphs, probe bipartite distance-hereditary
graphs, and probe ptolemaic graphs where $n$ and $m$ are the numbers
of vertices and edges of the input graph respectively.

並列關鍵字

bipartite distance-hereditary graph ； distance-hereditary graph ； probe graph ； ptolemaic graph

參考文獻

trivially perfect graphs, Theoretical Computer Science 410 (2009),

Probe Graphs and Cycle-Bicolorable Graphs, SIAM Journal on Dis-

Philadelphia, 1999.

nition of probe cographs and partitioned probe distance hereditary

graphs, Proceedings of the 2nd International Conference on Algorithmic