跳到主要內容

臺灣博碩士論文加值系統

(35.172.223.30) 您好!臺灣時間:2021/07/25 12:13
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:洪綾珠
研究生(外文):Hung, Ling-Ju
論文名稱:一些探測圖類別之辨識演算法設計
論文名稱(外文):Recognition Algorithms for Some Probe Graph Classes
指導教授:張貿翔張貿翔引用關係羅曼斯吳邦一
指導教授(外文):Chang, Maw-ShangRossmanith, PeterWu, Bang Ye
口試委員:徐力行吳邦一張貿翔羅曼斯王有禮楊昌彪李新林彭勝龍
口試委員(外文):Hsu, Lih-HsingWu, Bang YeChang, Maw-ShangRossmanith, PeterWang, Yue-LiYang, Chang-BiauLee, Sing-LingPeng, Sheng-Lung
口試日期:2012-07-20
學位類別:博士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:117
中文關鍵詞:探測圖保距圖二分保距圖托勒密圖
外文關鍵詞:probe graphdistance-hereditary graphbipartite distance-hereditary graphptolemaic graph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:226
  • 評分評分:
  • 下載下載:20
  • 收藏至我的研究室書目清單書目收藏:0
令$\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.
1 Introduction 1
2 Preliminaries 6
2.1 Notation 6
2.2 Properties of DHGs and its subclasses 8
2.3 Properties of probe DHGs and its subclasses 14
2.4 An $O(n^3)$-time recognition algorithm 19
3 Partially partitioned probe DHG 22
3.1 Twins 22
3.2 Kernel probe graphs and Algorithm B 25
3.3 Non-biconnected probe graphs without twins and Algorithm R 41
3.4 Time complexity of the main algorithm 45
4 Partially partitioned probe BDHG 48
4.1 False twins 49
4.2 Kernel probe graphs and Algorithm B1 51
4.3 Non-biconnected probe graphs without false twins and Algorithm R1 59
4.4 Time complexity 66
5 Partially partitioned PPtG 68
5.1 Some properties for reducing the problem size 69
5.2 Algorithm PPtG 87
5.3 Time complexity 94
6 Conclusion 97
6.1 The recognition of unpartitioned probe G graphs 97
6.2 The Hamiltonian cycle problem 98
[1] H. J. Bandelt, and H. M. Mulder, Distance-hereditary graphs, Journal
of Combinatorial Theory, Series B 41 (1986), pp. 182–208.
[2] D. Bayer, V. B. Le, and H.N. de Ridder, Probe threshold and probe
trivially perfect graphs, Theoretical Computer Science 410 (2009),
pp. 4812–4822.
[3] A. Berry, E. Cohen, M. C. Golumbic, M. Lipshteyn, N. Pinet, A.
Sigayret, and M. Stern, Recognition chordal-bipartite probe graphs,
Research Report LIMOS/RR-07-09, 2007.
[4] A. Berry, M. C. Golumbic, and M. Lipshteyn, Recognizing Chordal
Probe Graphs and Cycle-Bicolorable Graphs, SIAM Journal on Dis-
crete Mathematics 21 (2007), pp. 573–591.
[5] A. Brandstädt, V. B. Le, and J. P. Spinrad, Graph classes: A sur-
vey, SIAM Monographs on Discrete Mathematics and Applications,
Philadelphia, 1999.
[6] D. B. Chandler, M.-S. Chang, T. Kloks, J. Liu, and S.-L. Peng, Recog-
nition of probe cographs and partitioned probe distance hereditary
graphs, Proceedings of the 2nd International Conference on Algorithmic
Aspects in Management (AAIM 2006), LNCS 4041 (2006), 267–278.
[7] D. B. Chandler, J. Guo, T. Kloks, and R. Niedermeier, Probe ma-
trix problems: totally balanced matrices, Proceedings of the 3rd Inter-
national Conference of Algorithmic Aspects on Management (AAIM
2007), LNCS 4508 (2007), pp. 368–377.
[8] D. B. Chandler, M.-S. Chang, T. Kloks, J. Liu, and S.-L. Peng, Par-
titioned probe comparability graphs, Theoretical Computer Science
396 (2008), pp. 212–222.
[9] D. B. Chandler, M.-S. Chang, T. Kloks, V. B. Le, and S.-L. Peng,
Probe ptolemaic graphs, Proceedings of the 14th Annual Interna-
tional Computing and Combinatorics Conference (COCOON 2008),
LNCS 5092 (2008), pp. 468–477.
[10] D. B. Chandler, M.-S. Chang, A. J.J. Kloks, J. Liu, and S.-L. Peng, On
probe permutation graphs, Discrete Applied Mathematics 157 (2009),
pp. 2611–2619.
[11] D. B. Chandler, M.-S. Chang, T. Kloks, and S.-L. Peng, Probe graphs.
Manuscript, 2009
http://www.cs.ccu.edu.tw/~hunglc/ProbeGraphs.pdf
[12] G. J. Chang, A. J. J. Kloks, J. Liu, and S.-L. Peng, The PIGs
full monty - a floor show of minimal separators, Proceedings of the
22nd Annual Symposium on Theoretical Aspects of Computer Science
(STACS 2005), LNCS 3404 (2005), pp. 521–532.
[13] G. J. Chang, T. Kloks, and S.-L. Peng, Probe interval bigraphs (ex-
tended abstract), Electronic Notes in Discrete Mathematics 19 (2005),
pp. 195–201.
[14] M.-S. Chang, T. Kloks, D. Kratsch, J. Liu, and S.-L. Peng, On the
recognition of probe graphs of some self-complementary classes of per-
fect graphs, Proceedings of the 11th Annual International Computing
and Combinatorics Conference (COCOON 2005), LNCS 3595 (2005),
pp. 808–817.
[15] M.-S. Chang, L.-J. Hung, and P. Rossmanith, Probe bipartite distance-
hereditary graphs, Proceedings of National Computer Symposium 2009:
Workshop on Algorithms and Bioinformatics, pp. 16–27.
[16] M.-S. Chang, L.-J. Hung, and P. Rossmanith, Probe distance-
hereditary graphs, Proceedings of the 16th Computing: the Australasian
Theory Symposium (CATS 2010), CRPIT 109 (2010), pp. 55–64.
[17] M.-S. Chang and L.-J. Hung, Recognition of probe ptolemaic
graphs (Extended Abstract), Proceedings of International Workshop
on Combinatorial Algorithms (IWOCA 2010), LNCS 6460 (2011),
pp. 286–290.
[18] M.-S. Chang, L.-J. Hung, T. Kloks, and S.-L. Peng, Block-graph width,
Theoretical Computer Science 412 (2011), pp. 2496–2502.
[19] M.-S. Chang, L.-J. Hung, and P. Rossmanith, Recognition of probe
distance-hereditary graph graphs, accepted by Discrete Applied Math-
ematics.
[20] B. Courcelle and S. Olariu, Upper bounds to the clique width of graphs,
Discrete Applied Mathematics 101 (2000), pp. 77–114.
[21] B. Courcelle, J. A. Makowsky, U. Rotics, Linear time solvable optimiza-
tion problems on graphs of bounded clique-width, Theory Computing
Systems 33 (2000) pp. 125–150.
[22] A. D’Atri and M. Moscarini, Distance-hereditary graphs, Steiner trees,
and connected domination, SIAM Journal on Computing 17 (1988),
pp. 521–538.
[23] M.C. Golumbic, H. Kaplan, and R. Shamir, Graph sandwich problems,
Journal of Algorithms 19 (1995), pp. 449–473.
[24] M. C. Golumbic, M. Lipshteyn, Chordal probe graphs, Discrete Applied
Mathematics 43 (2004), pp. 221–237.
[25] M. C. Golumbic, F. Maffray, and G. Morel, A characterization of chain
probe graphs, Annals of Operations Research 188 (2011), pp. 175–183.
[26] P. L. Hammer and F. Maffray, Completely separable graphs, Discrete
Applied Mathematics 27 (1990), pp. 85–99.
[27] A. Hertz, Slim graphs, Graphs and Combinatorics 5 (1989), pp. 149–
157.
[28] P. Hlinˇ en´ y and S. Oum, Finding branch-decomposition and rank-
decomposition, SIAM Journal on Computing 38 (2008), pp. 1012–1032.
[29] E. Howorka, A characterization of distance-hereditary graphs, The
Quarterly Journal of Mathematics 28 (1977), pp. 417–420.
[30] E. Howorka, A characterization of ptolemaic graphs, Journal of Graph
Theory 5 (1981), pp. 323–331.
[31] R.-W. Hung, S. C. Wu, and M.-S. Chang, Hamiltonian cycle problem
on distance-hereditary graphs, Journal of Information Science and En-
gineering 19, pp. 827–838.
[32] L.-J. Hung, T. Kloks, and C. M. Lee, Trivially-perfect width, in
Proceedings of International Workshop on Combinatorial Algorithms
(IWOCA 2009), LNCS 5874 (2009), pp. 301–311.
[33] J. L. Johnson and J. Spinrad, A polynomial-time recognition algorithm
for probe interval graphs, Proceedings of the 12th Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA 2001), pp. 477–486.
[34] J.-M. Lanlignel and E. Thierry, Pruning graphs with digital search
trees. Application to distance hereditary graphs, Proceedings of the
17th Annual Symposium on Theoretical Aspects of Computer Science
(STACS 2000), LNCS 1770 (2000), pp. 529–541.
[35] V. B. Le and H. N. de Ridder, Characterisations and linear-time recog-
nition of probe cographs. Proceedings of the 33rd International Work-
shop on Graph-Theoretic Concepts in Computer Science (WG 2007),
LNCS 4769 (2007), pp. 226–237.
[36] V. B. Le, Two characterization of chain partitioned probe graphs, An-
nals of Operations Research 188 (2011), pp. 279–283.
[37] R. M. McConnell and J. P. Spinrad, Construction of probe interval
graphs, Proceedings of the 13th ACM-SIAM Symposium on Discrete
Algorithms (SODA 2002), pp. 866–875.
[38] R. M. McConnell and Y. Nussbaum, Linear-time recognition of probe
interval graphs, Proceedings of the 17th Annual European Symposium
on Algorithms (ESA 2009), LNCS 5757 (2009), pp. 349–360.
[39] S. Oum, Rank-width and vertex-minors, Journal of Combinatorial The-
ory, Series B 95 (2005), pp. 79–100.
[40] S. Oum, Graphs of bounded rank-width. PhD Thesis. Princeton Univer-
sity, Princeton (2005).
[41] S. Oum, Approximating rank-width and clique-width quickly, ACM
Transactions on Algorithms 5, No. 1, Article 10, 2008.
[42] P. E. Zhang, A. Schon, S. G. Fischer, E. Cayanis, J. Weiss, S. Kistler,
and E. Bourne, An algorithm based on graph theory for the assem-
bly of contigs in physical mapping of DNA, Bioinformatics 10 (1994),
pp. 309–317.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top