臺灣博碩士論文加值系統

一個圖形中若不含大於長度三的迴路，則我們稱此圖為弦圖。一個圖形G 的樹寬（最少填入邊）問題，即是找一個弦圖包含G，使得最大的完全子圖必須為最小（填入邊數最少）。對一般圖而言，樹寬和最少填入邊問題都是NP-complete，即使在一些特殊圖如雙分圖、雙分圖的補圖等也都是NP-complete。在這一篇論文中我們提出了一個
一致的演算法來解決雙分排列圖上樹寬和最少填入邊問題，我們的演算法執行時間是線性的。前人最佳的結果需要花Ｏ(n2)的時間，（n 是輸入圖中點的個數。）

A graph is chordal if every cycle of length greater than three has a chord. The
treewidth (respectively, minimum ll-in) problem is to nd a chordal supergraph
with the smallest possible maximum clique size (respectively, the minimum number of
additional edges). Similarly, the pathwidth (respectively, interval graph completion)
problem is to nd a interval supergraph with the smallest possible maximum clique
size (respectively, the minimum number of additional edges). Both problems are NPcomplete
on general graphs. They remain NP-complete even for cobipartite graphs,
bipartite graphs and graphs of clique size at most 9. A bipartite permutation graph is
a both bipartite and permutation graph. In this thesis, we present a uni ed approach
to compute the treewidth and minimum ll-in on bipartite permutation graphs in
linear time. The best previous result is O(n2) where n is the number of vertices in
the input graph.

Abstract i
Acknowledgement ii
Contents iii
List of Figures v
List of Tables vii
1 Introduction 1
2 Preliminaries 7
2.1 De nitions about related graph classes . . . . . . . . . . . . . . . . . 7
2.2 Treewidth and minimum ll-in . . . . . . . . . . . . . . . . . . . . . . 13
3 Main Results 19
3.1 Biclique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 A uni ed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Concluding Remarks 31
Bibliography 32

[1] N. Abbas and L. K. Stewart. Biconvex graphs: ordering and algorithms. Discrete
Applied Mathematics, 103:1{19, 2000.
[2] S. Arnborg, D. G. Corneil, and A. Proskurowski. Complexity of nding embeddings
in a k-tree. SIAM Journal of Algebraic and Discrete Methods, 8:277{284,
1987.
[3] S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems
restricted to partial k-tree. Discrete Applied Mathematics, 23:11{24, 1989.
[4] H. L. Bodlaender. A linear time algorithm for nding tree-decompositions of
small treewidth. Proceedings of the 25th Annual ACM Symposium on Theory of
Computing, pages 226{234, 1993.
[5] H. L. Bodlaender. A tourist guide through treewidth. Acta Cybernetica, 11:1{23,
1993.
[6] H. L. Bodlaender, T. Kloks, and D. Kratsch. Treewidth and pathwidht of permutation
graphs. SIAM Journal on Graph Discrete Mathematics, 8:606{616,
1995.
[7] H. L. Bodlaender, T. Kloks, D. Kratsch, and H. Muller. Treewidth and minimum
ll-in on d-trapezoid graphs. Journal of Graph Algorithms and Applications, 2:1{
23, 1998.
[8] H. L. Bodlaender and R. H. Mohring. The pathwidth and treewidth of cographs.
SIAM Journal on Discrete Mathematics, 6:181{188, 1993.
[9] H. L. Bodlaender and D. M. Thilikos. Treewidth and small separators for graphs
with small chordality. Technical Report UU-CS-1995-02, Department of Computer
Science, Utrecht University, Utrecht, 1995.
[10] H. Broersma, E. Dahlhaus, and T. Kloks. A linear time algorithm for minimum
ll in and treewidth for distance hereditary graphs. Scienti c program 5th Twente
Workshop on Graphs and Combinatorial Optimization, pages 48{50, 1997.
[11] M. S. Chang. Algorithms for maximum matching and minimum ll-in on chordal
bipartite graphs. Proceedings of the 7th International Symposium Algorithms and
Computation, pages 146{155, 1996.
[12] G. Chartrand and O. R. Oellermann. Applied and Algorithmic Graph Theory.
McGraw-Hill, 1993.
[13] G. A. Dirac. On rigid circuit graphs. Abhandlungen aus dem Mathematischen
Seminar der Universitat Hamburg, 25:71{76, 1961.
[14] G. A. Dirac. Cographs: recognition, applications and algorithms. Congressus
Numerantium, 43:249{258, 1984.