距離繼承圖上的最長路徑問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：8

、訪客IP：18.191.245.229

姓名

郭易祿(Yi-Lu Guo) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

距離繼承圖上的最長路徑問題
(The Longest Path Problem on Distance-hereditary Graphs)

相關論文

★ 一種減輕LEO衛星網路干擾的方案	★ 萃取駕駛人在不同環境之駕駛行為方法
★ 非地面網路中基於位置的隨機接入分配方法	★ TrustFADE: 針對可程式化邏輯區塊之安全認證方法
★ 捷徑問題在特殊圖形上之演算研究	★ 行動電腦教室與其管理系統的設計與建置
★ 蛋白質體視覺化系統之實作	★ 最小切割樹群聚演算法極端情形之研究
★ 教室內應用無線科技之一對一數位學習模式	★ 蛋白質交互作用網路之視覺化系統
★ 以賓果式遊戲輔助技巧熟練之數位學習環境設計與實作	★ 蛋白質註解的三維視覺化工具
★ Joyce 2：一個在一對一數位教室環境下之小組競爭遊戲	★ 同儕計算網路上內文散佈演算法之實作與效能評估
★ 在直角多邊形上使用基因演算法畫樹之研究	★ 經由潛在語義的線索從蛋白質交互作用網路進行蛋白質功能的預測

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

中文摘要
在本論文中，我們於距離繼承圖中求解最長路徑問題。所謂的最長路徑問題即為於圖形中找出一條最長的簡單路徑問題，為漢彌爾頓路徑問題的一般化，故於一般圖形中求解難度為一NP-complete問題。所謂的距離繼承圖其性質為：對於圖上任意兩點，其間的的最短距離於任何原圖的誘導子圖中都相同。本篇論文利用距離繼承圖的特性，於O(n4)時間內求解距離繼承圖上的最長路徑問題。

摘要(英)

Abstract.
The longest path problem is to find a path of maximum length in a graph. As a generalization of Hamiltonian path problem, it is NP-complete on general graphs. A graph is called distance-hereditary if the distance of each pair of vertices in every connected induced subgraph containing them are the same. In this dissertation, we present an O(n4) time algorithm to solve the longest path problem on a distance-hereditary graph of n vertices.

關鍵字(中)

★ 最長路徑問題
★ 距離繼承圖
★ 多項式時間演算法

關鍵字(英)

★ Longest path problem
★ Distance-hereditary graphs
★ Polynomial-time algorithms

論文目次

Table of Contents
中文摘要. i
Abstract. ii
誌謝 iii
Table of Contents iv
List of Figures v
Chapter 1. Introduction 1
Chapter 2. Related Works 4
2.1 Block Graphs and Cactus Graphs 4
2.2 Cographs 5
2.3 Bipartite Permutation Graphs 6
2.4 Interval Graphs 8
2.5 Ptolemaic Graphs 9
Chapter 3. Preliminaries 11
Chapter 4. Crucial Path Sets 14
Chapter 5. The Algorithm of the Longest Path Problem 20
5.1 Computation of Crucial Path Sets 20
5.2 Solving the Longest Path Problem 22
Chapter 6. Conclusion Remarks 25
Reference. 27

參考文獻

[1] Arikati, S.R., and Pandu Rangan, C. “Linear algorithm for optimal path cover problem Son interval graphs.” Inf. Process. Lett. pp. 149-153, 1990.
[2] Asdre, K., and Nikolopoulos, S.D. “The 1-fixed-endpoint path cover problem is polynomial on interval graphs”. Algorithmica, pp. 679-710, 2009.
[3] Bandelt, H.J., and Mulder, H.M. “Distance-hereditary graphs”, Journal of Combinatorial Theory Series B, Vol. 41, pp. 182-208, 1989.
[4] Berge, C. Graphs and Hypergraphs, North-Holland, Amsterdam , 1973.
[5] Bertossi, A.A. “Finding Hamiltonian circuits in proper interval graphs.” Inf. Process. Lett. pp. 97–101, 1983.
[6] Brandstädt, A., and Dragan, F.F. “A linear-time algorithm for connected-domination and Steiner tree on distance-hereditary graphs”, Networks Vol. 31, No. 3, pp. 177-182, 1998.
[7] Brandstädt, A., Le, V.B., and Spinrad, J.P., “Graph Classes: A Survey”, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 1999.
[8] Bulterman, R., van der Sommen, F., Zwaan, G., Verhoeff, T., van Gasteren, A., and Feijen, W. “On computing a longest path in a tree”. Inf. Process. Lett. Vol.81, pp. 93-96, 2002.
[9] Chang, M.S., Hsieh, S.Y., and Chen, G.H. ”Dynamic programming on distance-hereditary graphs”, Proceedings of Seventh International Symposium on Algorithms and Computation (ISAAC’97), Lecture Notes in Computer Science, vol. 1350, pp.344-353, 1997.
[10] Chang, M.S., Peng, S.L., and Liaw, J.L. “Deferred-query: an efficient approach for some problems on interval graphs”. Networks Vol. 34, pp. 1-10, 1999.
[11] Corneil, D.G., Lerchs, H., and Stewart, L.K. “Complement reducible graphs”, Discrete Appl. Math. Vol. 3, pp. 163-174 ,1981.
[12] Corneil, D.G., Perl, Y., and Stewart, L.K. “A linear recognition algorithm for cographs,” SIAM J. Comput. Vol. 14, pp. 926-934, 1985.
[13] D’atri, A., and Moscarini, M. “Distance-hereditary graphs, Steiner trees, and connected domination,” SIAM J. Comput. Vol. 17, No. 3, pp. 521-538, 1988.
[14] Damaschke, P. “The Hamiltonian circuit problem for circle graphs is NP-complete.” Inf. Process. Lett. Vol. 32, pp. 1-2, 1989.
[15] Damaschke, P. “Paths in interval graphs and circular arc graphs.” Discrete Math. Vol. 112, pp.49-64, 1993.
[16] Damaschke, P., Deogun, J.S., Kratsch, D., and Steiner, G. “Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm.” Order Vol. 8, pp. 383-391, 1992.
[17] Dragan, F.F. “Dominating cliques in distance-hereditary graphs,” Algorithm Theory SWAT’94 Fourth Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 824, Springer, Berlin, pp. 370-381, 1994.
[18] Howorka, E., A characterization of ptolemaic graphs, Journal of Graph Theory 5, pp. 323~331, 1981.
[19] Garey, M.R., and Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York (1979)
[20] Garey, M.R., Johnson, D.S., and Tarjan R.E. “The planar Hamiltonian circuit problem is NP-complete.” SIAM J. Comput. Vol. 5, pp. 704-714, 1976.
[21] Golumbic, M.C. Algorithmic Graph Theory and Perfect Graphs, Academic press, NewYork (1980)
[22] Golumbic, M.C. Algorithmic Graph Theory and Perfect Graphs.” Annals of Discrete Mathematics, Vol. 57. North-Holland, Amsterdam , 2004.
[23] Hammer, P.L., and Maffray, F. “Complete separable graphs,” Discrete Appl. Math. Vol. 27, NO. 1, pp. 85-99, 1990.
[24] Howorka, E. “A characterization of distance-hereditary graphs”, Quarterly Journal of Mathematics (Oxford), Vol. 28, No. 2, pp. 417-420, 1977.
[25] Howorka, E. “A characterization of Ptolemaic graphs”, Journal of Graph Theory Vol. 5, pp. 323-331, 1981.
[26] Hsieh, S.Y. “Parallel decomposition of distance-hereditary graphs,” Proceedings of the Fourth International ACPC Conference Including Special Tracks on Parallel Numerics (ParNum’99) and Parallel Computing in Image Processing, Video Processing, and Multimedia (ACPC’99), Lecture Notes in Computer Science, Vol. 1557, pp. 417–426, 1999.
[27] Hsieh, S.Y., Ho, C.W., Hsu, T.S., Ko, M.T., and Chen, G.H. “Efficient parallel algorithms on distance-hereditary graphs,” Parallel Process. Lett. Vol. 9, No. 1, pp. 43-52, 1999.
[28] Hsieh, S.Y., Ho, C.W., Hsu, T.S., Ko, M.T., and Chen, G.H. “A faster implementation of a parallel tree contraction scheme and its application on distance-hereditary graphs,” J. Algorithms, Vol. 35, pp. 50-81, 2000.
[29] Hsieh, S.Y., Ho, C.W., Hsu, T.S., Ko, M.T., and Chen, G.H. “Characterization of efficient parallel solvable problems on distance-hereditary graphs,” SIAM J. Discrete Math. Vol. 15, No. 4, pp. 488-518, 2002.
[30] Hsieh, S.Y., Ho, C.W., Hsu, T.S., and Ko, M.T. “The Hamiltonian problem on distance-hereditary graphs,” Discrete Applied Math. Vol. 154, pp. 508-524, 2006.
[31] Hung, R.W., Wu, S.C., and Chang, M.S. “Hamiltonian cycle problem on distance-hereditary graphs,” J. Inform. Sci. Engrg. Vol. 19, pp. 827-838, 2003.
[32] Hung, R.W., and Chang, M.S. “Finding a minimum path cover of a distance-hereditary graph in polynomial time,” Discrete Applied Math. Vol. 155, pp. 2242-2256, 2007.
[33] Itai, A., Papadimitriou, C.H., and Szwarcfiter, J.L. “Hamiltonian paths in grid graphs.” SIAM J. Comput. Vol. 11, pp. 676-686, 1982.
[34] Ioannidou, K., Mertzios, G.B., and Nikolopoulos, S.D. “The Longest Path Problem has a Polynomial Solution on Interval Graphs,” Algorithmica, Vol. 61, No. 2, pp. 320-341, 2011.
[35] Keshavarz-Kohjerdi, F., and Bagheri, A., “An efficient parallel algorithm for the longest pathproblem in meshes”, Discrete Appl. Math., Volume 160, pp.210-217, 2012.
[36] Kirkpatrick, D.G., Reddy, K.M., Rangan, C.P., and Srinivasan, A, “Partial and perfect path covers of cographs”, Discrete Appl. Math., Volume 89, pp. 143-153, 1998.
[37] Mertzios, G.B., and Corneil, D.G., “A Simple Polynomial Algorithm for the Longest Path Problem on Comparability Graphs”, arXiv:1004.4560v1, 2010.
[38] Müller, H., and Nicolai, F. “Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs,” Inform. Process., Lett. Vol 46, pp. 225-230, 1993.
[39] Müller, H. “Hamiltonian circuits in chordal bipartite graphs.” Discrete Math. Vol. 156, pp. 291-298, 1996.
[40] Narasimhan, G. “A note on the Hamiltonian circuit problem on directed path graphs.” Inf. Process. Lett. Vol. 32, pp. 167-170, 1989.
[41] Nicolai, F. “Hamiltonian problems on distance-hereditary graphs,” Technique report, Gerhard-Mercator University, Germany, 1994.
[42] Takahara, Y., Teramoto, S., and Uehara, R. “Longest path problems on Ptolemaic graphs.” IEICE Trans. Inf. Syst. Vol. 91-D, pp.170-177, 2008
[43] Uehara, R., and Uno, Y. “Efficient algorithms for the longest path problem.” Proc. of the 15th Annual International Symp. on Algorithms and Computation (ISAAC). LNCS, Vol. 3341, pp. 871-883. Springer, Berlin , 2004.
[44] Uehara, R., and Valiente, G. “Linear structure of bipartite permutation graphs and the longest path problem.” Inf. Process. Lett. Vol. 103, pp. 71-77, 2007.
[45] Yeh, H.G., and Chang, G.J. “Weighted connected domination and Steiner trees in distance-hereditary graphs,” Discrete Appl. Math. Vol. 87, pp. 245-253, 1998.
[46] Yeh, H.G., and Chang, G.J. Linear-time algorithms for bipartite distance-hereditary graphs, Manuscript.
[47] Yeh, H.G., and Chang, G.J. “The path-partition problem in bipartite distance-hereditary graphs,” Taiwanese J. Math.Vol. 2, No. 3, pp. 353-360, 1998.
[48] Yeh, H.G., and Chang, G.J. “Weighted connected k-domination and weighted k-dominating clique in distance-hereditary graphs,” Theoret. Comput. Sci. Vol. 263, pp. 3-8, 2001.

指導教授

何錦文(Chin-Wen Ho)

審核日期

2013-7-11

推文