臺灣博碩士論文加值系統

Berry [A. Berry, J. P. Bordat, Moplex elimination orderings, Electronic Notes in Discrete Mathematics, 8 (2001) 6--9] 證明圖 G 為弦圖，若且唯若此圖會有 moplex 順序。在本篇論文中，我們證明了強弦圖上亦有類似的順序，將此命名為 simple moplex 順序。而且，我們提出了一個演算法，在線性時間計算出該順序。

Berry [A. Berry, J. P. Bordat, Moplex elimination orderings, Electronic Notes in Discrete Mathematics, 8 (2001) 6--9] proved that a graph G is choral if and only if G admits a moplex ordering. In this thesis, we also prove that a strongly chordal graph has a similar ordering namely simple moplex ordering. Then, we propose an algorithm that can be run in linear time to find such an ordering.

摘 要.................................................I
Abstract........................................... II
誌 謝................................................III
目錄 ................................................V
表目錄.............................................VII
圖目錄..............................................IX
1 緒論...............................................1
1.1研究動機...................................1
1.2名詞與符號定義.........................6
2 文獻探討.......................................12
3 Simple Moplex 順序.....................18
3.1存在性證明..................................18
3.2演算法.........................................23
4 結論及未來研究方向.......................29
4.1結論........................................29
4.2未來研究方向............................29
參考文獻...........................................30

[1] G. Ausiello, A. D'Atri, M. Moscarini, Chordality properties on graphs and minimal conceptual connections in semantic data models, Journal of Computer and System Sciences, 33 (1986) 179-202.

[2] A. Berry, J. P. Bordat, Separability generalizes Dirac's theorem, Discrete Applied Mathematics,84 (1998) 43-53.

[3] A. Berry, J. P. Bordat, O. Cogies, Generating all the minimal separators of a graph, International Journal of Foundations of Computer Science, 11 (2000) 397-404.

[4] A. Berry, J. P. Bordat, Moplex elimination orderings,Electronic Notes in Discrete Mathematics, 8 (2001) 6-9.

[5] A. Berry, R. Pogorelcnik, A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph, Information Processing Letters, 111 (2011) 508-511.

[6] A. Berry, R. Pogorelcnik, G. Simonet, Organizing the atoms of the clique separator decomposition into an atom tree, Discrete Applied Mathematics,In Press, Corrected Proof — Note to users.

[7] J. R. S. Blair, B. Peyton, An Introduction to Chordal Graphs and Clique Trees, Mathematics and its Applications ,56 (1993) 1--29.

[8] G. J. Chang, G. L. Nemhauser, The k-domination and k-stability problems on sun-free chordal graphs, SIAM Journal on Algebraic Discrete Methods, 5 (1984) 332-345.

[9] L. S. Chandran, F. Grandoni, A linear time algorithm to list the minimal separators of chordal graphs, Discrete Mathematics, 306 (2006) 351-358.

[10] G. A. Dirac, On rigid circuit graphs, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 25 (1961) 71-76.

[11] F. F. Dragan, K. F. Prisakar', V. D. Chepoi, The location problem on graphs and the helly problem, Diskretnaya Mathematika, 4 (1992) 67-73.

[12] M. Farber, Characterization of strongly chordal graphs, Discrete Mathematics, 43 (1983) 173-189.

[13] H. de Fraysseix, P. Ossona de Mendez,Planarity and edge poset dimension, European Journal of Combinatorics, 17 (1996) 731-740.

[14] D. R. Fulkerson and O. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics, 15 (1965) 835-855.

[15] M. C. Golumbic, C. F. Goss, Perfect Elimination and Chordal Bipartite Graphs, Journal of Graph Theory, 2 (1978) 155-163.

[16] A. J. Hoffman, A. W. J. Kolen, and M. Sakarovitch, Totally-balanced and greedy matrices, SIAM Journal on Algebraic and Discrete Methods,
6 (1985) 721-730.

[17] T. Kloks, D. Kratsch, Listing all minimal separators of a graph, SIAM Journal on Computing, 27 (1998) 605-613.

[18] D. Kratsch, The structure of graphs and the design of efficient algorithms, Hanliltation thesis, (1995) Friedric-Schiller-Universität,Jena.

[19] P. S. Kumar, C. E. V. Madhavan, Minimal vertex separators of chordal graphs, Discrete Applied Mathematics, 89 (1998) 155-168.

[20] A. Lubiw, Doubly lexical orderings of matrices, SIAM journal on Computing, 16 (1987) 854-879.

[21] M. Moscarini, Doubly chordal graphs, steiner trees, and connected domination, Networks, 23 (1993) 59-69.

[22] R. H. Möhring, F. J. Radermacher, Substitution decomposition for discrete structures and connections with combinatorial optimization, Annals of discrete mathematics, 19 (1984) 257-356.

[23] R. Paige and R. E. Tarjan, Three partition refinement algorithms, SIAM Journal on Computing, 16 (1987) 973-989.

[24] N. K. R. Prasad and P. S. Kumar, On generating strong elimination orderings of strongly chordal graphs, Foundations of Software Technology and Theoretical Computer Science Lecture Notes in Computer Science, 1530 (1998) 221-232.

[25] F. S. Roberts, Indifference graphs, in: F. Harary (Ed.), Proof Techniques in Graph Theory, Academic Press, New York (1969) 139-146.

[26] D. Rose, R. E. Tarjan, G. Lueker, Algorithmic aspects of vertex elimination, SIAM journal on Computing, 5 (1976) 266-283.

[27] J. Sawada, J. P. Spinrad, From a simple elimination ordering to a strong elimination ordering in linear time, Information Processing Letters, 86 (2003) 299-302.

[28] W. Schnyder, Planar graphs and poset dimension, Order, 5 (1989) 323-343.

[29] H. Shen, W.-F. Liang, Efficient enumeration of all minimal separators in a graph, Theoretical Computer Science, 180 (1997) 169-180.

[30] J. P. Spinrad, Doubly lexical ordering of dense 0–1 matrices, Information Processing Letters, 45 (1993) 229-235.

[31] R. E. Tarjan, M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, 13 (1984) 565-579.

[32] R. Uehara, Linear time algorithms on chordal bipartite and strongly chordal graphs, International Colloquium on Automata, Languages and Programming.(2002), 993-1004.

[33] H.-L. Wang, W.-L. Chiang, A linear time algorithm for the simple moplex ordering of a strongly chordal graph, Proceeding of the 31th Workshop on Combinatorial and Computation Theory.(2014), 171-173.

[34] D. B. West, Introduction to Graph Theory, Prentice Hall, 2001.

[35] S.-J. Xu, X.-Y. Li, R.-H. Liang, Moplex orderings generated by the LexDFS algorithm, Discrete Applied Mathematics. 161 (2013), 2189-2195.