臺灣博碩士論文加值系統

在圖形搜尋問題中，起始圖形的所有邊是被污染的，我們的目的是使用最少個數的搜尋者將所有的邊清乾淨，這個搜尋者的數目稱為此圖形的搜尋數，而一個搜尋策略則是一連串可以清乾淨整個圖形的合法動作，一個搜尋策略使用的搜尋者數目若等於這個圖形的搜尋數，則稱其為最佳的搜尋策略。
本論文考慮三種版本的圖形搜尋問題，分別是點搜尋、邊搜尋和混合搜尋。在點搜尋中，清一個邊必須在其二端點上各站一個搜尋者；在邊搜尋中，一個邊必須由一個搜尋者走過才算清乾淨；而在混合搜尋中，清邊的方法可以是點或邊搜尋的清邊方法。針對這三個搜尋問題，我們在幾類特殊圖上提出有效率的演算法。
樹是我們研究的特殊圖之一，在點搜尋問題上，Scheffler提出了一個相當複雜的線性演算法來計算一個樹的點搜尋數，並宣稱其演算法可以修改來建構該樹的一個最佳的點搜尋策略。不幸地，該文獻上並沒有詳細記載修改的方式。Ellis等人使用不同的方法提出了一個線性演算法來計算一個含有n點的樹的點搜尋數和一個O(nlogn) 的演算法來建構該樹的一個最佳的點搜尋策略，並提出：是否存在一個線性演算法來建構該樹的一個最佳點搜尋策略？
在邊搜尋問題上，Megiddo等人提出了一個線性演算法來計算一個樹的邊搜尋數，然而他們用來建構該樹最佳邊搜尋策略的演算法需要O(nlogn) 的時間。在混合搜尋上也有類似的結果，Takahashi等人提出了一個線性演算法來計算一個樹的混合搜尋數和一個O(nlogn) 的演算法來建構該樹的一個最佳混合搜尋策略。一個公開問題是：是否存在一個線性演算法來建構該樹的一個最佳的邊搜尋（和混合搜尋）策略？
在本論文中，我們將邊搜尋裡樹的主軸觀念（Megiddo等人提出）擴充為延伸主軸且適用於這三種搜尋問題，我們更進一步提出了樹的延伸主軸系統觀念，一個延伸主軸系統可以被轉換成一個最佳的搜尋策略，如果這個延伸主軸系統被製作於一個樹狀結構上（稱為主軸樹），那麼這個轉換只需要線性時間，在點搜尋和混合搜尋裡，我們設計了一個線性演算法來建構一個主軸樹，如此一個樹的最佳點搜尋（和混合搜尋）策略可以在線性時間內獲得。
此外，藉由延伸主軸系統，我們證明了在點搜尋和邊搜尋中存在著一種關係，也就是說，對任一個發芽樹（最少含四個點、沒有度數為二的點且每一個內部的點都接有葉點）而言，它在點搜尋中的一個延伸主軸系統也是一個在邊搜尋中的一個延伸主軸系統，反之亦然。任何一個樹只要不是一個路徑圖，都可以被轉換成一個發芽樹，我們證明了一個樹的邊搜尋數等於它的發芽樹的邊搜尋數，所以由我們所建立的關係，一個樹的最佳邊搜尋策略可以由其發芽樹的最佳點搜尋策略得到，換句話說，一個樹的最加邊搜尋策略可以在線性時間內獲得。
似星圖是另一個我們所研究的特殊圖，Gustedt證明了每一個似星圖都有一個正規化的最佳點搜尋策略（在這個策略中，最大完全子圖是一個接一個的被清乾淨），他提出了一個O(n2k+1) 時間和空間的演算法在k-似星圖上（k≧1），n為輸入圖的點數。在相同的問題和圖上，我們導出了對於一個k-似星圖擁有一個給定搜尋數的充分且必要條件，藉由檢查這些條件，我們得到了一個O(mnk) 時間和O(m) 空間的演算法，m為輸入圖的邊數。
對於邊搜尋和混合搜尋，我們也導出了類似但更複雜的充分且必要條件，這個結果使得邊搜尋和混合搜尋問題分別在分裂圖上有O(mn2) 時間與O(m) 空間的演算法和在k-似星圖（k≧2）上有O(mnk) 時間與O(m) 空間的演算法，這些問題以前並沒有任何人提出演算法。此外，我們也證明了邊搜尋和混合搜尋問題在弦圖上是NP-complete。對於這二個問題，我們在區間圖上提出了線性演算法。

In the graph searching problem, initially a graph with all its edges
contaminated is presented.
The objective is to obtain a state of the graph in
which all the edges are simultaneously cleared by using the least
number of searchers.
This number is called the search number of the graph.
A search strategy is a sequence of allowable moves that clears the
initial contaminated graph.
A search strategy is optimal if the number of searchers used is
equal to the search number of the graph.
Three variations of the graph searching problem are considered.
They are node searching, edge searching and mixed searching.
In node searching, an edge is cleared by concurrently having searchers
on both of its endpoints.
In edge searching, an edge is cleared by moving a searcher
along this edge.
In mixed searching, an edge can be cleared either by node searching
rules or by edge searching rules.
For these problems on several special classes of graphs,
we provide efficient algorithms
The class of trees is one of the studied special classes of graphs.
For the node searching problem, Scheffler presented a fairly
complicate linear-time algorithm to compute the node-search number of
a tree $T$ and claimed that a linear-time algorithm for constructing
an optimal node-search strategy of $T$ easily followed.
Unfortunately, few details of her construction are recorded in the
literature.
Using an approach different from Scheffler''s, Ellis {\it et al}.
proposed algorithms to compute the node-search number of an $n$-vertex
tree $T$ in $O(n)$ time and to construct an optimal node-search strategy
of $T$ in $O(n\log n)$ time.
An open problem was proposed whether there exists a linear-time
algorithm to construct an optimal node-search strategy of $T$.
For the edge searching problem, Megiddo {\it et al}. proposed a
linear-time algorithm to compute the edge-search number of $T$.
However, their algorithm runs in $O(n\log n)$ time for
constructing an optimal edge-search strategy of $T$.
A similar result for the mixed searching problem on trees is shown
by Takahashi {\it et al}.
They also proposed an $O(n)$-time algorithm to compute the
mixed-search number of $T$ and an $O(n\log n)$-time algorithm
to construct an optimal mixed-search strategy of $T$.
An open problem was also proposed whether there exists a linear-time
algorithm to construct an optimal edge-search (and mixed-search)
strategy of $T$.
In this dissertation, we extend the concept of avenue on a tree
in edge searching, proposed by Megiddo {\it et al}., to extended
avenue for these three searching problems.
Moreover, we propose the concept of extended avenue system of a tree
for these three searching problems.
An extended avenue system can be transformed to an optimal
search strategy and this transformation can be done in linear
time if the extended avenue system is implemented by a tree
structure, called avenue tree.
In node searching and mixed searching, we design a linear-time
algorithm to construct an avenue tree for a tree and an
optimal node-search (mixed-search) strategy is thus obtained
in linear time.
Furthermore, we show that there is a relationship between node searching
and edge searching by considering their extended avenue systems respectively.
In fact, we show that an extended avenue system in node searching
is also an extended avenue system in edge searching and {\it vice versa} for
any sprout tree in which there are at least four vertices with no
degree-2 vertex and every internal vertex is adjacent to at least one leaf.
For any tree $T$ which is not a path can be transformed into a sprout
tree $T^{ rime}$.
We show that the edge-search number of $T$ is equal to the edge-search number
of $T^{ rime}$.
Hence, by the relationship we mentioned above, an optimal edge-search strategy
of $T$ can be obtained from an optimal node-search strategy of $T^{ rime}$.
That is, an optimal edge-search strategy of $T$ can be obtained in
linear time.
The class of starlike graphs is another special class of graphs we
have studied on the graph searching problem.
Gustedt show that every starlike graph has a normalized optimal node-search
strategy in which the maximal cliques are cleared one by one.
By using a dynamic programming approach, he gave an $O(n^{2k+1})$-time and
-space algorithm for the node searching problem on $k$-starlike
graphs for a fixed $k \geq 1$, where $n$ is the number of vertices in
the input graph.
For the same problem, we derive necessary and sufficient
conditions for a $k$-starlike graph to have a given node-search number.
By checking these conditions, it leads to an $O(mn^{k})$-time
and $O(m)$-space algorithm on $k$-starlike graphs for a fixed $k \geq 1$,
where $m$ is the number of edges in the input graph.
For edge searching and mixed searching, we also derive similar but
more complicated necessary and sufficient conditions respectively.
It leads to an $O(mn^{2})$-time and $O(m)$-space algorithm on split graphs
and an $O(mn^{k})$-time and $O(m)$-space algorithm on $k$-starlike graphs
for a fixed $k \geq 2$ for the edge and mixed searching problems.
There is no polynomial algorithm known
previously for the edge and mixed searching problems.
In addition, we also show that the
edge and mixed searching problems remain NP-complete on chordal graphs.
As a by-product, we propose linear time algorithms on interval graphs for
the edge and mixed searching problems.

封面
Acknowledgments
Abstract
List of Tables
List of Figures
Chapter 1 Introduction
Chapter 2 Preliminaries
2.1 Notation and Definitions
2.2 Properties on edge searching
2.3 Basic results
Chapter 3 Graph searching on trees
3.1 The avenue and hub
3.2 The extended avenue system and avenue tree
3.3 Constructiong optimal node- and mixed-search strategies
3.4 Relating the node and edge searching
Chapter 4 Graph searching on split graphs
4.1 Edge searching
4.2 Mixed searching
Chapter 5 Graph searching on κ-starlike graphs
5.1 Node searching
5.2 Edge searching
5.3 Mixed searching
5.4 NP-complete results on starlike graphs
Chapter 6 Graph searching on interval graphs
6.1 Edge seraching
6.2 Mixed searching
Chapter 7 Concluding remarks and future works
Bibliography

[1] S. Arnborg, D.G. Corneil, and A. Proskurowski,
Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic
Discrete Methods, 8(1987), 277-284.
[2] D. Bienstock, Graph searching, path-width, tree-width and
related problems (a survey), in: F. Roberts, F. Hwang and C. Monma, eds.,
Reliability of Computer and Communication Networks,
DIMACS series in Discrete Mathematics and Theoretical Computer Science,
Vol 5, American Mathematic Society, 1991, 33-49.
[3] H.L. Bodlaender, A partial $k$-arboretum of
graphs with bounded treewidth, Technical Report UU-CS-1996-02,
Department of Computer Science, Utrecht University, the Netherlands,
1996.
[4] H.L. Bodlaender and T. Kloks, Efficient and
constructive algorithms for the pathwidth and treewidth of graphs,
Journal of Algorithms, 21(1996), 358-402.
[5] H.L. Bodlaender, T. Kloks, and D. Kratsch,
Treewidth and pathwidth of permutation graphs, SIAM Journal on Discrete
Mathematics, 8(1995), 606-616.
[6] H.L. Bodlaender, T. Kloks, D. Kratsch, and H.
M\"{u}ller, Treewidth and minimum fill-in on d-trapezoid graphs,
Technical Report UU-CS-1995-34, Department of Computer Science, Utrecht
University, Utrecht, the Netherlands, 1995.
[7] K.S. Booth and G.S. Leuker, Testing for consecutive
ones property, interval graphs and graph planarity using PQ-tree algorithms,
Journal of Computer System and Science, 13(1976), 335-379.
[8] H.L. Bodlaender and R.H. M\"{o}hring, The pathwidth and
treewidth of cographs, SIAM Journal on Discrete Mathematics, 6(1993),
181-188.
[9] D. Bienstock and P. Seymour, Monotonicity in graph
searching, Journal of Algorithms, 12(1991), 239-245.
[10] A. Brandst\"{a}dt, J. Spinrad and L. Stewart,
Bipartite permutation graphs are bipartite tolerance graphs,
Congressus Numerantium, 58(1987), 165-174.
[11] Ruay-Shung Chang, Single step graph search problem,
Information Processing Letters, 40(1991), 107-111.
[12] Ruay-Shung Chang, An optimal algorithm for edge searching
an interval graph, Journal of Information Science and Engineering,
9(1993), 421-430.
[13] Ruay-Shung Chang, J.Y. Hsiao and Chuan Yi Tang,
Solving the single step graph searching problem by solving the maximum
two-independent set problem, Information Processing Letters,
40(1991), 283-287.
[14] T.H. Cormen, C.E., Leiserson and R.L. Rivest,
Introduction to algorithms, The MIT Press, 1992.
[15] D.G. Corneil, H. Lerchs and L. Stewart-Burlingham,
Complement reducible graphs, Discrete Applied Mathematics,
3(1981), 163-174.
[16] Moon-Jung Chung, F. Makedon, I.H. Sudborough, and J.
Turner, Polynomial time algorithms for the min cut problem on degree
restricted trees, SIAM Journal on Computing, 14(1985), 158-177.
[17] I. Dagan, M.C. Golumbic and I. Pinter, Trapezoid graphs
and their coloring, Discrete Applied Mathematics, 21(1988),
35-46.
[18] N.D. Dendris, L.M. Kirousis and D.M. Thilikos,
Fugitive-search games on graphs and related parameters,
Theoretical Computer Science, 172(1997), 233-254.
[19] S. Even, A. Pnueli and A. Lempel, Permutation graphs
and transitive graphs, Journal of the Association Computing Machinery,
19(1972), 400-410.
[20] J.A. Ellis, I.H. Sudborough, and J.S. Turner, The
vertex separation and search number of a graph, Information and
Computation, 113(1994), 50-79.
[21] M. Farber, Characterizations of strongly chordal graphs,
Discrete Mathematics, 43(1983), 173-189.
[22] C. Flotow, On powers of $m$-trapezoid graphs,
Discrete Applied Mathematics, 63(1995), 187-192.
[23] F.V. Fomin, Helicopter search problems, bandwidth and pathwidth,
Discrete Applied Mathematics, 85(1998), 59-70.
[24] F.V. Fomin and N.N. Petrov, Pursuit-evasion
and search problems on graphs, Congressus Numerantium, 122(1996), 47-58.
[25] F. Gavril, The intersection graphs of subtrees in
trees are exactly the chordal graphs, Journal of Combinatorial Theory
Ser. B, 16(1974), 47-56.
[26] F. Gavril, A recognition algorithm for the intersection
graphs of directed paths in directed trees, Discrete Mathematics,
13(1975), 237-249.
[27] M.C. Golumbic, Algorithmic graph theory and
perfect graphs, Academic Press, New York, 1980.
[28] P.A. Golovach, Extremal searching problems on
graphs, Ph. D. thesis, Leningrad, 1990 (in Russian).
[29] P.A. Golovach, Search number, node search number,
and vertex separator of a graph, Vestnik Leningradskogo Universiteta.
Mathematika, 24(1991), 88-90.
[30] J. Gustedt, On the pathwidth of chordal graphs,
Discrete Applied Mathematics, 45(1993), 233-248.
[31] P.C. Gilmore and A.J. Hoffman, A characterization of
comparability graphs and of interval graphs, Can. J. Math.,
16(1964), 539-548.
[32] P.A. Golovach and N.N. Petrov, The search number of
a complete graph, Vestnik Leningradskogo Universiteta.
Mathematika, 19(1986), 15-19.
[33] F. Harary, A characterization of block graphs,
Canadian Mathematic Bull, 6(1963), 1-6.
[34] E. Howorka, On metric properties of certain clique graphs,
Journal of Combinatorial Theory Ser. B, 27(1979), 67-74.
[35] M. Habib and R.H. M\"{o}hring, Treewidth of cocomparability
graphs and a new order-theoretical parameter, Order, 11(1994), 47-60.
[36] P.L. Hammer and B. Simeone, The splittance of a
graph, Combinatorica, 1(1981), 275-284.
[37] N.G. Kinnersley, The vertex separation number of a
graph equals its path-width, Information Processing Letters, 42(1992),
345-350.
[38] T. Kloks, Treewidth--computations and approximations,
Lecture Note in Computer Science 842, Springer-Verlag, Berlin, 1994.
[39] T. Kloks, H. Bodlaender, H. M\"{u}ller, and D.
Kratsch, Computing treewidth and minimum fill-in: all you need are the
minimal separators, ESA''93, Lecture Note in Computer Science 726,
260-271, 1993. Erratum: ESA''94,
Lecture Note in Computer Science 855, pp. 508, 1994.
[40] T. Kloks, K. Kratsch and H. M\"{u}ller, Dominoes, WG''94,
Lecture Note in Computer Science 903, 106-120, 1995.
[41] L.M. Kirousis and C.H. Papadimitriou, Interval graph
and searching, Discrete Mathematics, 55(1985), 181-184.
[42] L.M. Kirousis and C.H. Papadimitriou, Searching and
pebbling, Theoretical Computer Science, 47(1986), 205-218.
[43] A. Kornai and Z. Tuza, Narrowness, pathwidth, and
their application in natural language processing,
Discrete Applied Mathematics, 36(1992), 87-92.
[44] A.S. LaPaugh, Recontamination does not help to search a graph,
Journal of the Association Computing Machinery, 40(1993), 224-245.
[45] N. Megiddo, S.L. Hakimi, M.R. Garey, D.S. Johnson, and
C.H. Papadimitriou, The complexity of searching a graph,
Journal of the Association Computing Machinery, 35(1988), 18-44.
[46] R.H. M\"{o}hring, Graph problems related to gate matrix
layout and PLA folding, in: G. Tinnhofer et al., eds., Computational
Graph Theory (Springer, Wien, 1990), 17-32.
[47] R.H. M\"{o}hring, Triangulating graphs without asteroidal
triples, Discrete Applied Mathematics, 64(1996), 281-287.
[48] F. Makedon and I.H. Sudborough, On minimizing width
in linear layouts, Discrete Applied Mathematics, 23(1989), 243-265.
[49] B. Monien and I.H. Sudborough, Min cut is NP-complete for edge
weighted trees, Theoretical Computer Science, 58(1988), 209-229.
[50] F. Makedon, C.H. Papadimitriou and I.H. Sudborough, Topological
bandwidth, SIAM Journal on Algebraic Discrete Methods, 6(1985), 418-444.
[51] T.D. Parsons, Pursuit-evasion in a graph, in Y.
Alavi and D.R. Lick, eds., Theory and applications of graphs,
Springer-Verlag, New York, 1976, 426-441.
[52] T.D. Parsons, The search number of a connected
graph, Proc. 9th S-E Conf. on Combinatorics, Graph Theory, and Computing,
549-554, 1978.
[53] N.N. Petrov, Pursuit problems without information
about the evader, Differents. Uravn., 18(1982), 1345-1352.
[54] Sheng-Lung Peng, Ming-Tat Ko, Chin-Wen Ho, Tsan-sheng Hsu, and
Chuan Yi Tang, Graph searching on chordal graphs, ISAAC''96,
Lecture Notes in Computer Science, 1178, 156-165, 1996.
[55] Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, and
Chuan Yi Tang, Edge and node searching problems on trees, to appear in
Theoretical Computer Science, an extended abstract of this paper appears in
COCOON''97, Lecture Note in Computer Science 1276, 284-293, 1997.
[56] Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, and
Chuan Yi Tang, A linear-time algorithm for constructing an optimal node-search
strategy of a tree, COCOON''98, Lecture Note in Computer Science 1449,
279-288, 1998.
[57] Sheng-Lung Peng, Ming-Tat Ko, Chin-Wen Ho, Tsan-sheng Hsu, and
Chuan Yi Tang, Graph searching on some subclasses of chordal graphs,
to appear in Algorithmica.
[58] N.N. Petrov and S.A. Starostina, Minimal graphs with
a search number less than four, Vestnik Leningradskogo Universiteta.
Mathematika, 22(1989), 66-68.
[59] A. Parra and P. Scheffler, How to use the minimal separators of
a graph for its chordal triangulation, ICALP''95, Lecture Note in Computer
Science 944, 123-134, 1995.
[60] A. Parra and P. Scheffler, Characterizations and algorithmic
applications of chordal graph embeddings, Discrete Applied Mathematics,
79(1997), 171-188.
[61] N. Robertson and P.D. Seymour, Graph minors I. Excluding a forest,
Journal of Combinatorial Theory Ser. B, 35(1983), 39-61.
[62] P. Scheffler, A linear algorithm for the pathwidth
of trees, in: R. Bodendiek and R. Henn, eds., Topics in Combinatorics
and Graph Theory (Physica-Verlag, Heidelberg, 1990), 613-620.
[63] P. Scheffler, Optimal embedding of a tree into an
interval graph in linear time, Fourth Czechoslovakian Symposium on
Combinatorics, Graphs and Complexity, in: J. Nesetril and M. Fiedler, eds.,
Annals of Discrete Mathematics 51 (North-Holland, 1992),
287-291.
[64] P.D. Seymour and R. Thomas, Graph searching and a minimax theorem
for tree-width, Journal of Combinatorial Theory Ser. B, 58(1993), 22-33.
[65] A. Takahashi, S. Ueno, and Y. Kajitani, On the
proper-path-decomposition of trees, Technical Report, CAS 91-74, IEICE,
1991.
[66] A. Takahashi, S. Ueno, and Y. Kajitani, Mixed-searching and
proper-path-width, Theoretical Computer Science, 137(1995), 253-268.
[67] M. Yannakakis, A polynomial algorithm for the min-cut linear
arrangement of trees, Journal of the Association Computing Machinery,
32(1988), 950-959.