捷徑問題在特殊圖形上之演算研究; Algorithmic Aspects of Some Geodetic Problems in Special Graphs

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/8403

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/8403

Title:	捷徑問題在特殊圖形上之演算研究;Algorithmic Aspects of Some Geodetic Problems in Special Graphs
Authors:	張肇明;Jou-Ming Chang
Contributors:	資訊工程研究所
Keywords:	二分排列圖;捷徑連通值;無樞紐圖;無AT圖;二分弦圖;識別演算法;區段圖;強弦圖;hinge-free graphs;asteroidal triple-free graphs;chordal bipartite graphs;recognition algorithms;interval graphs;artite permutation graphs;geodetic connectivity;strongly chordal graphs
Date:	2001-07-24
Issue Date:	2009-09-22 11:26:03 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	本篇論文的主要內容，在於考慮若干個與圖形有關的捷徑問題。論文的第一部份主要在探討圖形之捷徑連通問題的演算複雜度，其動機乃基於此問題可應用至網路的設計與分析。我們除了提出一O(nm)時間的演算法以解決任意圖形的捷徑連通問題外，並特別著重於探討在特殊圖形下，捷徑連通問題的演算複雜度是否可有效降低。我們的結果顯示﹕在弦圖之下的強弦圖、托勒密圖和區段圖，均可在線性時間內解決此問題﹔無向路徑圖則需O(n^2)時間得解。另外，因為許多種類的連結網路均可由多次的線圖運算反覆生成，所以我們亦解決了無樞紐點之線圖的識別問題。最後，我們提出若干作用於圖形上的運算，利用這些運算，圖形得以在不破壞捷徑連通性之下作擴張。論文的第二部份旨在建立一無AT圖的特殊節點次序，並以此節點次序為主，延伸其相關的討論。我們證明一連通無AT圖必具有一特殊節點次序，稱之為2-比較補圖次序。此節點次序可以距離測度加以表示，對於某些演算頗有助益。在無AT圖上，我們可利用演進序列和2次LexBFS的技巧建立此一次序。這種新的節點次序實際上即為比較補圖次序的推廣。利用2-比較補圖次序，我們得證無AT圖的任一冪次圖均為一比較補圖，並以更有效的方法解決了無AT圖的k-統治、k-穩定及k-叢集等問題。更甚者，利用以2次LexBFS所得之2-比較補圖次序，可在線性時間內求得無AT圖的4-擴張樹，或在同樣時間內識別二分排列圖。最後，我們探討二分弦圖的特性，並證明二分弦圖上的任意節點對之最短路徑長度問題可在O(n^2)的最佳時間內得解。另外，我們亦深入研究圖形叢集問題的演算複雜度。所謂圖形的叢集問題就是﹕給定一上界，是否存在有一種節點的叢集方式可將圖形分割成若干子圖，使得各個子圖的直徑不超過此一上界。針對此問題，我們就若干特殊圖形類別研究，分別得到了NP-complete 和多項式時間的解。 In this dissertation, several geodetic problems in graphs are considered. The motivation of studying geodetic connectivity and hinge vertices in a graph arises naturally from network design and analysis. We first look at the algorithmic complexities of computing geodetic connectivity and finding all hinge vertices in a graph. We present an O(nm) time algorithm for solving this problem in an arbitrary graph. In particular, we are interested to know if there exist special classes of graphs with special properties such that the time complexity of determining whether a graph has geodetic connectivity k can be reduced. We investigate this topic on some special classes of chordal graphs. Linear time algorithms are developed for strongly chordal graphs, ptolemaic graphs, and interval graphs, and an O(n^2) time algorithm is proposed for undirected path graphs. Because many interconnection networks can be constructed using line graph iterations, we also study how to recognize line graphs without hinge vertices. Moreover, we provide several operations of graphs that allow a graph to expand in scale without destroying geodetically connectivity. Next, we deal with the topic on constructing a specific vertex ordering of an AT-free graph. We show that every connected AT-free graph admits a vertex ordering that we call a 2-cocomparability ordering. The ordering presented here can be defined by using the term of distance metric, and can be exploited for algorithmic purposes. Two techniques called involutive sequence and 2-sweep LexBFS are introduced for constructing such an ordering for AT-free graphs. This ordering generalizes the cocomparability ordering achievable for cocomparability graphs. According to this ordering, we show that every power of an AT-free graph is indeed a cocomparability graph. Also, it leads to that the distance k-domination, k-stability, and the graph k-clustering problems for k>=2 on AT-free graphs can be solved in a more efficient way. In particular, the vertex ordering produced from the 2-sweep LexBFS can be used for constructing a tree 4-spanner of an AT-free graph and for recognizing a class of special AT-free graphs called bipartite permutation graphs in linear time. Besides, we study the characterization of chordal bipartite graphs and show that the all-pairs-shortest-length problem on chordal bipartite graphs can be solved in O(n^2) optimal time. We further investigate the algorithmic complexity of a graph clustering problem that determine whether there is a partition of a graph into certain number clusters of vertices such that the diameter of subgraph induced by each cluster does not exceed a prespecified bound. Some NP-complete and polynomial results are derived for several classes of special graphs.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...