Abstract
本篇論文探討了資訊科學領域中相當基礎且重要的兩個研究議題： 字串索引問題及找尋互斥路徑問題。 本論文的第一部分探討下列三個有位置限制的字串索引問題： 特定位置之後的字串索引問題、區間範圍內的字串索引問題、以及包含 variable-length don't care 符號的字串索引問題。過去的結果主要是依賴解決 the range successor problem 的資料結構作為工具，所以只要 range successor 這個問題的資料結構有任何的改進，就可以得到這三個問題的改進結果。在這篇論文中，我們首先針對 range successor 這個問題提出三個新的索引資料結構。更明確地說，我們提出了 (1) 一個使用 n + o(n) 空間且支援 O(log n / loglog n) 查詢時間的資料結構，此結果的查詢時間比先前使用相同空間的資料結構快 O(loglog n) 倍；(2) 一個使用 O(n loglog n) 空間且支援 O((loglog n)^2) 查詢時間的資料結構，此結果的空間時間乘積優於過去所有的結果；以及 (3) 一個使用 O(n^{1+\epsilon}) 空間且支援 O(1) 查詢時間的資料結構，此結果比先前有相同複雜度的資料結構簡單許多。此外，第二個資料結構也可以用來解決在 R^3 空間中一個稱為 orthogonal range successor problem 的重要問題，使用 O(n log^{1+\epsilon} n) 空間且支援 O(log n loglog n) 查詢時間；這個結果改進了過去已經存在很久的最好結果。 利用我們在 range successor 這個問題上的改進結果，上述三個有位置限制的字串索引問題在任意大小的字符集下都可以被立刻改進。在現實生活的應用中，字符集通常很小，因此在本論文中，我們也探討了在小字符集下的上述三個字串索引問題。當字符集大小是 O(polylog(n)) 時，我們為這些問題提出了更有效率的改進演算法。針對第一個與第三個問題，我們提出了使用 O(n) 空間且支援 O(p) 查詢時間的最佳資料結構。針對第二個問題，我們提出了一個使用 O(n log^\epsilon n) 空間且支援 O(p) 查詢時間的資料結構；與一個使用 O(n) 空間且支援 O(p + occ log^\epsilon n) 查詢時間的資料結構。當字符集大小是 O(polylog(n)) 時，我們的演算法改進了過去所有的結果。 這篇論文的第二部分探討以下兩個問題： 在一個無向平面圖中找尋兩條有長度限制的點互斥路徑問題、以及在一個有向無循環圖中找尋 k 條點互斥路徑且讓最長路徑最小化的問題。針對第一個問題，我們提出一個改進演算法，時間與空間的複雜度分別為 O(n^3 b_min) 與 O(n^2 b_min)，其中 b_min 為兩個給定的長度限制中較小的一個。針對第二個問題，我們提出了一個改進的演算法與一個更快的完全多項式時間近似方案 (fully polynomial-time approximation scheme)。提出的改進演算法使用了 O(n^{k+1} M^{k-1}) 時間與 O(n^k M^{k-1}) 空間；而提出的近似方案使用了 O((1/\epsilon)^{k-1} n^{2k} log^{k-1} M) 時間與 O((1/\epsilon)^{k-1} n^{2k-1} log^{k-1} M) 空間，其中 \epsilon 為給定的近似參數、M 為最佳解中最長路徑的長度。