博碩士論文 84345009 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:10 、訪客IP:3.228.24.192
姓名 張肇明( Jou-Ming Chang)  查詢紙本館藏   畢業系所 資訊工程學系
論文名稱 捷徑問題在特殊圖形上之演算研究
(Algorithmic Aspects of Some Geodetic Problems in Special Graphs)
相關論文
★ 行動電腦教室與其管理系統的設計與建置★ 蛋白質體視覺化系統之實作
★ 最小切割樹群聚演算法極端情形之研究★ 教室內應用無線科技之一對一數位學習模式
★ 蛋白質交互作用網路之視覺化系統★ 以賓果式遊戲輔助技巧熟練之數位學習環境設計與實作
★ 蛋白質註解的三維視覺化工具★ Joyce 2:一個在一對一數位教室環境下之小組競爭遊戲
★ 同儕計算網路上內文散佈演算法之實作與效能評估★ 在直角多邊形上使用基因演算法畫樹之研究
★ 經由潛在語義的線索從蛋白質交互作用網路進行蛋白質功能的預測★ 從生物文件中萃取出蛋白質或基因之名稱
★ 利用蛋白質交互作用網路偵測必要性蛋白質★ 族群基因繪圖演算法的改良
★ 設計與實做一對一數位教室環境與元件交換社群★ 行動科技對經驗學習之支援性
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 本篇論文的主要內容,在於考慮若干個與圖形有關的捷徑問題。論文的第一部份主要在探討圖形之捷徑連通問題的演算複雜度,其動機乃基於此問題可應用至網路的設計與分析。我們除了提出一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.
關鍵字(中) ★ 二分排列圖
★ 捷徑連通值
★ 無樞紐圖
★ 無AT圖
★ 二分弦圖
★ 識別演算法
★ 區段圖
★ 強弦圖
關鍵字(英) ★ hinge-free graphs
★ asteroidal triple-free graphs
★ chordal bipartite graphs
★ recognition algorithms
★ interval graphs
★ artite permutation graphs
★ geodetic connectivity
★ strongly chordal graphs
論文目次 Cover
Contents
1. Introduction
1.1. Motivations and Intentions
1.2. Outline of the Dissertation
2. Preliminaries
2.1. Graph Terminology and Notations
2.2. Graph Classes
3. Geodetic Connectivity
3.1. Computing Geodetic Connectivity in Graphs
3.2. Geodetic Connectivity in Special Graphs
3.3. Recognizing Hinge-free Line Graphs and Total Graphs
3.4. Constructing Geodetically Connected Graphs on Large Scale
4. Distance in Asteroidal Triple-free Graphs
4.1. A Generalization of Cocomparability Graphs
4.2. AT-free Graphs Are 2-Cocomparability Graphs
4.3. Recognition of Bipartite Permutation Graphs
4.4. AT-free Graphs Are Tree 4-Spanner Admissible
5. All-Pairs-Shortest-Length Problem
5.1. Characterizations of Chordal Bipartite Graphs
5.2. Solving APSL Problem on Chordal Bipartite Graphs
6. Graph Clustering into Subgraphs with Bounded Diameter
6.1. NP-Complete Results
6.2. Polynomial Cases Using the Reduction of Graph Powers
7. Concluding Remarks
參考文獻 N. Abbas and L. Stewart, Clustering bipartite and chordal graphs: complexity, sequential andparallel algorithms, Discrete Applied Mathematics, 91 (1999) pp. 1--23.
R. P. Anstee and M. Farber, On bridged graphs and cop-win graphs, Journal of Combinatorial Theory (B), 44 (1988) pp. 22--28.
K. Arvind, H. Breu, M. S. Chang, D. G. Kirkpatrick, F. Y. Lee, Y. D. Liang, K. Madhukar, C. P. Rangan, and A. Srinivasan, Efficient algorithms in cocomparability and trapezoid graphs, manuscript (1996).
M. J. Atallah, D. Z. Chen, and D. T. Lee, An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications, Algorithmica, 14 (1995) pp. 429--441.
G. Ausiello, A. D'Atri, and M. Moscarini, Chordality properties on graphs and minimal conceptual connections in semantic data models, Journal of Computer and System Sciences, 33 (1986) pp. 179--202.
V. Balachandhran and C. P. Rangan, All-pairs-shortest-length on strongly chordal graphs, Discrete Applied Mathematics, 69 (1996) pp. 169--182.
H. Balakrishnan, A. Rajaraman, and C. P. Rangan, Connected domination and steiner set on Asteroidal triple-free graphs, in: Proceedings of International Workshop on Algorithms and Data Structures (WADS'93), Lecture Notes in Computer Science Vol. 709, Springer-Verlag, (1993) pp. 131--141.
H. J. Bandelt and H. M. Mulder, Distance-hereditary graphs, Journal of Combinatorial Theory Series (B), 41 (1986) pp. 182--208.
L. W. Beineke, Derived graphs and digraphs, Beitr "age zur Graphentheorie (Teubner, Leipzig, 1968).
C. Berge, Les probl `emes de coloration en the 'eorie des graphes, Publ. Inst. Statnt. Univ. Paris, 9 (1960) pp. 123--160.
K. S. Booth and G. S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences, 13 (1976) pp. 335--379.
A. Brandst "adt, Classes of bipartite graphs related to chordal graphs, Discrete Applied Mathematics, 32 (1991) pp. 51--60.
A. Brandst "adt, V. D. Chepoi, and F. F. Dragan, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Discrete Applied Mathematics, 82 (1998) pp. 43--77.
A. Brandst "adt, F. F. Dragan, V. D. Chepoi, and V. I. Voloshin, Dually chordal graphs, SIAM Journal on Discrete Mathematics, 11 (1998) pp. 437--455.
A. Brandst "adt, F. F. Dragan, and F. Nicolai, Homogeneously orderable graphs, Theoretical Computer Science, 172 (1997) pp. 209--232.
A. Brandst "adt, V. B. Le, and J. P. Spinrad, Graph Classes: A Survey, (series SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, PA, 1999).
A. Brandst "adt, V. B. Le, and T. Szymczak, Duchet-type theorems for powers of HHD-free graphs, Discrete Mathematics, 177 (1997) pp. 9--16.
A. Brandst "adt, J. Spinrad, and L. Stewart,
Bipartite permutation graphs and bipartite tolerance graphs,
Congressus Numerantium 58 (1987) pp. 165--174.
G. Brassard and P. Bratley, Algorithmics: theory and practice (Prentice-Hall, Englewood Cliffs, 1988).
H. Broersma, T. Kloks, D. Kratsch, and H. M "uller, Independent sets in asteroidal triple-free graphs, SIAM Journal on Discrete Mathematics, 12 (1999) pp. 276--287.
N. G. de Bruijn, A combinatorial problem, in :Proceedings Koninklijke Nederlandse Academie van Wetenschappen Ser. A 49 (1946) pp. 758--764.
F. Buckley and F. Harary, Distance in Graphs (Addison-Wesly, Redwood City, California, 1990).
L. Cai, Tree spanners: spanning trees that approximate distance, Tech. Rept. 260/92, Department of Computer Science, University of Toronto (1992).
L. Cai and D. G. Corneil, Tree spanners, SIAM Journal on Discrete Mathematics, 8 (1995) pp. 359--387.
R. Chandrasekaran and A. Doughety, Location on tree networks: p-center and q-dispersion problems, Mathematics of Operations Research, 6 (1981) pp. 50--57.
M. S. Chang, Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs, in: Proceedings of the 7th Annual International Symposium on Algorithms and Computation (ISAAC'96), Lecture Notes in Computer Science Vol. 1178 (1996) pp. 146-155.
G. J. Chang and G. L. Nemhauser, The k-domination and k-stability problems on sun-free chordal graphs, SIAM Journal on Algebraic and Discrete Methods 5 (1984) pp. 332--345.
J. M. Chang and C. W. Ho, The recognition of geodetically connected graphs, Information Processing Letters, 65 (1998) pp. 81--88.
J. M. Chang and C. W. Ho, Recognizing hinge-free line graphs and total graphs, to appear in Taiwanese Journal of Mathematics.
J. M. Chang, C. W. Ho, and M. T. Ko, LexBFS-ordering in asteroidal triple-free graphs, in: Proceedings of 10th Annual International Symposium on Algorithms and Computation (ISAAC'99), Lecture Notes in Computer Science Vol. 1741, Springer-Verlag, (1999) pp. 163--172.
J. M. Chang, C. W. Ho, and M. T. Ko, Powers of asteroidal triple-free graphs with applications, to appear in Ars Combinaatoria.
J. M. Chang, C. W. Ho, C. C. Hsu, and Y. L. Wang, The characterizations of hinge-free networks, in: Proceedings of International Computer Symposium, Workshop on Algorithms, (1996) pp. 105--112.
J. M. Chang, C. C. Hsu, Y. L. Wang, and T. Y. Ho, Finding the set of all hinge vertices for strongly chordal graphs in linear time, Information Science, 99 (1997) pp. 173--182.
H. S. Chao, F. R. Hsu, and R. C. T. Lee, On the shortest length queries for permutation graphs, in: Proceedings of International Computer Symposium, Workshop on Algorithms, (1998) pp. 132--138.
F. Cheah, A recognition algorithm for II-graphs, Doctoral thesis, Department of Computer Science, University of Toronto (1990).
L. Chen, Solving the shortest-paths problem on bipartite permutation graphs efficiently, Information Processing Letters, 55 (1995) pp. 259--264.
D. Z. Chen, D. T. Lee, R. Sridhar, and C. N. Sekharan, Solving the all-pair shortest path query problem on interval and circular-arc graphs, Networks, 31 (1998) pp. 249--258.
V. Chepoi, On distance-preserving and domination elimination orderings, SIAM Journal on Discrete Mathematics, 11 (1998) pp. 414--436.
D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, 9 (1990), pp. 251--280.
D. G. Corneil, H. Lerchs, and L. Stewart Burlingham, Complement reducible graphs, Discrete Applied Mathematics, 3 (1981) pp. 163--174.
D. G. Corneil, S. Olariu, and L. Stewart, A linear time algorithm to compute a dominating path in an AT-free graph, Information Processing Letters, 54 (1995) pp. 253--257.
D. G. Corneil, S. Olariu, and L. Stewart, Asteroidal triple-free graphs, SIAM Journal on Discrete Mathematics, 10 (1997) pp. 399--430.
D. G. Corneil, S. Olariu, and L. Stewart, The ultimate interval graph recognition algorithm? in: Proceedings of the 19th annual ACM-SIAM symposium on Discrete algorithms, (1998) pp. 175--180.
D. G. Corneil, S. Olariu, and L. Stewart, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, SIAM Journal on Computing, 28 (1999) pp. 1284--1297.
D. G. Corneil, Y. Perl, and L. K. Stewart, A linear recognition algorithm for cographs, SIAM Journal on Computing, 14 (1985) pp. 926--934.
E. Dahlhaus, Optimal (parallel) algorithms for the all-to-all vertices distance problem for certain graph classes, in: Proceedings of 18th International Workshop Graph-Theoretic Concepts in Computer Science (WG'92), Lecture Notes in Computer Science Vol. 657 (1992) pp. 60--69.
E. Dahlhaus and P. Duchet, On strongly chordal graphs, Ars Combinatoria, 24B (1987) pp. 23--30.
P. Damaschke, Distances in cocomparability graphs and their powers, Discrete Applied Mathematics, 35 (1992) pp. 67--72.
J. S. Deogun, D. Kratsch, and G. Steiner, An approximation algorithm for clustering graphs with dominating diametral path, Information Processing Letters, 61 (1997) pp. 121--127.
G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25 (1961) pp. 71--76.
F. F. Dragan and F. Nicolai, LexBFS-ordering of distance-hereditary graphs, Technical Report Gerhard-Mercator-Universit "at-Gesamthochschule Duisburg SM-DU-303.
F. F. Dragan, F. Nicolai, and A. Brandst "adt, Powers of HHD-free graphs, International Journal of Computer Mathematics, 69 (1998) pp. 217--242.
P. Duchet, Classical perfect graphs, Annals of Discrete Mathematics, 21 (1984) pp. 67--96.
R. C. Entringer, D. E. Jackson, and P. J. Slater, Geodetic connectivity of graphs, IEEE Transactions on Circuits Systems, CAS-24 (1977) pp. 460--463.
M. Farber, Characterizations of strongly chordal graphs, Discrete Mathematics, 43 (1983) pp. 173--189.
M. Farber, Domination, independent domination, and duality in strongly chordal graphs, Discrete Applied Mathematics, 7 (1984) pp. 115--130.
M. Farber and R. E. Jamison, Convexity in graphs and hypergraphs, SIAM Journal on Algebraic and Discrete Methods, 7 (1986) pp. 433--444.
A. M. Farley, S. Hedetniemi, and A. Proskurowski, Partitioning trees: matching, domination, and maximum diameter, International Journal of Computer and Information Sciences, 10 (1981) pp. 55--61.
A. M. Farley and A. Proskurowski, Self-repairing networks, Parallel Processing Letter, 3 (1993) pp. 381--391.
M. A. Fiol, J. L. A. Yebra, and I. Alegre, Line digraph iterations and the (d,k) digraph problem, IEEE Transactions on Computers, C-33 (1984) pp. 400--403.
C. Flotow, On powers of m-trapezoid graphs, Discrete Applied Mathematics, 63 (1995) pp. 187--192.
R. W. Floyd, Algorithm 97 (SHORTEST PATH), Communication ACM, 5 (1962) pp. 345.
D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics, 15 (1965) pp. 835--855.
T. Gallai, Transitiv orientierbare Graphen, Acta Mathematica Academiae Scientiarum Hungaricae, 18 (1967) pp. 25--66.
M. R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, (Freeman, San Francisco, 1979).
F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM Journal on Computing, 1 (1972) pp. 180--187.
F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, Journal of Combinatorial Theory (B), 16 (1974) pp. 47--56.
F. Gavril, A recognition algorithm for the intersection graphs of paths in trees, Discrete Mathematics, 23 (1978) pp. 211--227.
P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canadian Journal Mathematics, 16 (1964) pp. 539--548.
M. Gionfriddo, A short survey on some generalized colourings of graphs, Ars Combinatoria, 30 (1986) 275--284.
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, (Academic Press, New York, 1980).
M. Gr "otschel, L. Lov 'asz, and A. Schrijver, Polynomial algorithms for perfect graphs, Annals of Discrete Mathematics, 21 (1984) pp. 325--356.
M. Habib, R. M. McConnell, C. Paul, and L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Science, 234 (2000) pp. 59--84.
P. Hammer and F. Maffray, Completely separable graphs, Discrete Applied Mathematics, 27 (1990) pp. 85--99.
K. Han, C. N. Sekharan, and R. Sridha, Unified all-pairs shortest path algorithms in the chordal hierarchy, Discrete Applied Mathematics, 77 (1997) pp. 59--71.
F. Harary, Graph Theory, (Addison-Wesley, Reading, MA, 1969).
C. T. Ho `ang and B. A. Reed, P_4-comparability graphs, Discrete Mathematics, 74 (1989) pp. 173--200.
C. W. Ho and J. M. Chang, Solving the all-pairs-shortest-length problem on chordal bipartite graphs, Information Processing Letters, 69 (1999) pp. 87--93.
T. Y. Ho, Y. L. Wang, and M. T. Juan, A linear time algorithm for finding all hinge vertices of a permutation graph, Information Processing Letters, 59 (1996) pp. 103--107.
T. Y. Ho, J. M. Chang, and Y. L. Wang, On the powers of graphs with bounded asteroidal number, Discrete Mathematics, 223 (2000) pp. 125--133.
E. Howorka, A characterization of distance-hereditary graphs, Quarterly Journal of Mathematics Oxford Series (2), 28 (1977) pp. 417--420.
A. J. Hoffman, A. W. J. Kolen, and M. Sakarovitch, Totally-balanced and greedy matrices, SIAM Journal on Algebraic and Discrete Methods, 6 (1985) pp. 721--730.
E. Howorka, A characterization of ptolemaic graphs, Journal of Graph Theory, 5 (1981) pp. 323--331.
W. L. Hsu and K. H. Tsai, Linear time algorithms on circular-arc graphs, Information Processing Letters, 40 (1991) pp. 123--129.
W. L. Hsu and T. H. Ma, Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs, SIAM Journal on Computing, 28 (1999) pp. 1004--1020.
U. Huckenbeck, Extremal Paths in Graphs: Foundations, Search Strategies, and Related Topics (Akademie Verlag, Berlin, 1997).
M. Imase and M. Itoh, A design for directed graph with minimum diameter, IEEE Transactions on Computers C-32 (1983) pp. 782--784.
A. O. Ivanov and A. A. Tuzhilin, Minimal Networks: the Steiner Problem and Its Generalizations (CRC Press, Boca Raton, Florida, 1994).
B. Jamison and S. Olariu, On the semi-perfect elimination, Advances in Applied Mathematics, 9 (1988) pp. 364--376.
D. B. Johnson, Efficient algorithms for shortest paths in sparse networks, Journal of the ACM, 24 (1977) pp. 1--13.
T. Kloks and D. Kratsch, Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph, Information Processing Letters, 55 (1995) pp. 11--16.
T. Kloks, D. Kratsch, and H. M "uller, Approximating the bandwidth of asteroidal triple-free graphs, Journal of Algorithms, 32 (1999) pp. 41--57.
T. Kloks, D. Kratsch, and J. Spinrad, On treewidth and minimum fill-in of asteroidal triple-free graphs, Theoretical Computer Science, 175 (1997) pp. 309--335.
T. Kloks, H. M "uller, and C. K. Wong, Vertex ranking of asteroidal triple-free graphs, Information Processing Letters, 68 (1998) pp. 201--206.
E. K "ohler, Recognizing graphs without asteroidal triples, in: Proceedings of 26th International Workshop Graph-Theoretic Concepts in Computer Science (WG2000), Lecture Notes in Computer Science Vol.1928, Springer-Verlag, (2000) pp. 2551--266.
N. Korte and R. H. M "ohring, A incremental linear-time algorithm for recognizing interval graphs, SIAM Journal on Computing, 18 (1989) pp. 68--81.
D. Kratsch, Domination and total domination on asteroidal triple-free graphs, Discrete Applied Mathematics, 99 (2000) pp. 111--123.
H. O. Le and V. B. Le, Optimal tree 3-spanners in directed path graphs, Networks, 34 (1999) pp.81--87.
C. G. Lekkerkerker and J. C. Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, 51 (1962) pp. 45--64.
A. Lubiw, Doubly lexical orderings of matrices, SIAM Journal on Computing, 16 (1987) pp. 854--879.
M. S. Madanlal, G. Venkatesan, and C. P. Rangan, Tree 3-spanners on interval, permutation and regular bipartite graphs, Information Processing Letters, 59 (1996) pp. 97--102.
R. M. McConnell and J. P. Spinrad, Modular decomposition and transitive orientation, Discrete Mathematics, 201 (1999) pp. 189--241.
F. R. McMorris and D. R. Shier, Representing chordal graphs on K_{1,n, Comment. Math. Univ. Carolin., 24 (1983) pp. 489--494.
P. Mirchandani, A simple O(n^2) algorithm for the all-pairs shortest path problem on an interval graph, Networks, 27 (1996) pp. 215--217.
R. H. M "ohring, Algorithmic aspects of comparability graphs and interval graphs, in Graphs and Order, I. Rival ed. (D. Reidel Publishing company, Dordrecht, 1985) pp. 41--101.
H. M. Mulder, The structure of median graphs, Discrete Mathematics, 24 (1978) pp. 197--204.
R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Mathematics, 43 (1983) pp. 235--239.
R. Paige and R. E. Tarjan, Three partition refinement algorithms, SIAM Journal on Computing, 16 (1987) pp. 973--989.
A. Parra and P. Scheffler, Characterizations and algorithmic applications of chordal graph embeddings, Discrete Applied Mathematics, 79 (1997) pp. 171--188.
D. Peleg and J. D. Ullman, An optimal synchronizer for the hypercube, in: Proceedings of 6th ACM Symposium on Principles of Distributed Computing, (1987) pp. 77-85.
A. Pnueli, A. Lempel, and S. Even, Transitive orientation of graphs and identification of permutation graphs, Canadian Journal Mathematics, 23 (1971) 1pp. 60--175.
V. Radhakrishnan, H. B. Hunt III, and R. E. Stearns, On solving systems of linear equations and path problems for bounded-treewidth graphs, in: Proceedings of 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS'92), Lecture Notes in Computer Science Vol. 577 (1992) pp. 109--119
R. Ravi, M. V. Marathe, and C. P. Rangan, An Optimal algorithm to solve the all-pair shortest path problem on interval graphs, Networks, 22 (1992) pp. 21--35.
A. Raychaudhuri, On powers of interval and unit interval graphs, Congressus Numerantium, 59 (1987) pp. 235--242.
A. Raychaudhuri, On powers of strongly chordal and circular arc graphs, Ars Combinatoria, 34 (1992) pp. 147--160.
D, J. Rose, Triangulated graphs and the elimination process, Journal of Mathematical Analysis and Applications, 32 (1970) pp. 597--609.
D. J. Rose, A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, in Graph theory and Computing, R. C. Read ed. (Academic Press, New York, 1972).
D. J. Rose, R. E. Tarjan, and G. S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing, 5 (1976) pp. 266--283.
A. A. Sch "affer, A faster algorithm to recognize undirected path graphs, Discrete Applied Mathematics, 43 (1993) pp. 261--295.
R. Seidel, On the all-pairs-shortest-path problem in unweighted undirected graphs, Journal of Computer and System Sciences, 51 (1995) pp. 400--403.
A. P. Sprague, Recognition of bipartite permutation graphs, congressus Numerantium, 112 (1995) pp. 151-161.
R. Sridhar, D. Joshi, and N. Chandrasekharan, Efficient algorithms for shortest distance queries on interval, directed path and circular-arc graphs, in: Proceedings of 5th International Conference on Computing and Information (ICCI'93), (1993) pp. 31--35.
J. Spinrad, On comparability and permutation graphs, SIAM Journal on Computing 14 (1985) pp. 658--670.
J. P. Spinrad, Doubly lexical orderings of dense 0-1 matrices, Information Processing Letters, 45 (1993) pp. 229--235.
J. Spinrad, A. Brandst "adt, and L. Stewart, Bipartite permutation graphs, Discrete Applied Mathematics, 18 (1987) pp. 279--292.
L. Stewart, Cographs, a class of tree representable graphs, TR 126/78, Department of Computer Science, University of Toronto (1978).
R. E. Tarjan and M. Yanakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, 13 (1984) pp. 566--579.
J. R. Walter, Representations of chordal graphs as subtrees of a tree, Journal of Graph Theory, 2 (1978) pp. 265--267.
New illustrated webster's dictionary of the English Language, Pamco Publishing Company, Inc., 1992.
指導教授 何錦文(Chin-Wen Ho) 審核日期 2001-7-24
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明