跳到主要內容

臺灣博碩士論文加值系統

(44.200.77.92) 您好!臺灣時間:2024/03/01 08:15
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:盧錦隆
研究生(外文):Lu, Chin Lung
論文名稱:加權有效支配之研究
論文名稱(外文):On the Study of Weighted Efficient Domination
指導教授:唐傳義
指導教授(外文):Chuan Yi Tang
學位類別:博士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1998
畢業學年度:86
語文別:中文
論文頁數:78
中文關鍵詞:演算法加權有效支配加權有效邊支配
外文關鍵詞:AlgorithmsWeighted efficient dominationWeighted efficient edge domination
相關次數:
  • 被引用被引用:0
  • 點閱點閱:192
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在一個簡單圖 (simple graph) G = (V, E) 裡,一個點 (vertex) 可以
支配 (dominate) 自己以及其它與之相鄰的點。所謂的有效支配集
(efficient dominating set) 是指一個點的子集合 D 使得圖 G 中的每
一個點只能被 D 中唯一的某個點給支配。有效支配問題就是在圖 G 中找
一個點的個數是最小的有效支配集。假若每個點上皆有一個實數加權值,
那麼所謂的加權有效支配問題即在 G 中找一個有效支配集使得其點的加
權值的和越小越好。有效支配的研究在許多不同的電腦科學領域上,譬如
編碼理論、圖的嵌入、地理位置上設備的配置以及在平行系統上資源的配
置等等,皆有許多的應用。有效支配在一些圖上,包括 bipartite 圖、
chordal 圖和點分支 (degree) 不超過 3 的 planar 圖等,已被證明是
NP-complete 的問題(即不容易解的問題)。但其加權有效支配問題在許
多特殊圖上,如 trees、 series-parallel 圖、split 圖、block 圖、
interval 圖、cocomparability 圖和 circular-arc 圖,卻可以在多項
式時間 (polynomial time) 甚至線性時間 (linear time) 內被找出解來
。在這本論文集內,我們證明了在 planar bipartite 圖、planar
bipartite 的線圖 (line graphs) 和 chordal bipartite 圖上,有效支
配是NP-complete 的問題。同時,對加權有效支配問題,我們在
bipartite permutation 圖、permutation 圖、trapezoid 圖和
distance-hereditary 圖分別設計出計算時間為 O(|V|)、O(|V|+|E''|)、
O(|V|loglog|V|+|E''|) 和 O(|V|) 的演算法。註:|E''| 表示在 G 的互
補圖 (complement) 中所有邊 (edges) 的個數。另一方面,我們也在一
些特殊圖上對有效邊支配問題 (efficient edge domination problem)
做些探討與研究。該問題在一般的圖 (general graphs) 上已被證明是
NP-complete 的,但在 generalized series-parallel 圖和 interval
圖上是線性時間內可解的。至於其加權的有效邊支配問題,並沒有太多的
著作被發表。在這本論文集裡,我們證明了在 planar bipartite 圖上,
有效邊支配是 NP-complete 的問題,因此在 planar 圖和 bipartite 圖
上,該問題也是 NP-compelte。除此之外,對加權有效邊支配問題,我們
分別在 generalized series-parallel 圖和 chordal 圖上設計出計算時
間為 O(|V|+|E|) 的演算法。值得一提的是,在 chordal 圖上,加權有
效支配是 NP-complete 的問題,但加權有效邊支配卻是線性時間內可解
的問題。
Given a simple graph G=(V, E), a vertex v \in V is said to
dominate itself and all vertices u in V which are adjacent to v.
A subset D of V is called an efficient dominating set of G if
every vertex in V is dominated by exactly one vertex in D. The
efficient domination problem is to find an efficient dominating
set of G with the minimum cardinality. Suppose that each vertex
v in V is associated with a real number. Then, the weighted
efficient domination problem is to find an efficient dominating
set with the minimum weight in G. There are many interesting
applications for efficient domination in coding theory, graph
embedding, facility location on geographical area and resource
allocation in parallel processing system. It is well known that
the efficient domination problem is NP-complete for bipartite
graphs, chordal graphs and planar graphs of maximum degree
three. Much research has been devoted to investigating the
algorithmic complexity of the weighted efficientdomination
problem on other special classes of graphs, such as trees,
series-parallel graphs, split graphs, block graphs, interval
graphs, cocomparability graphs and circular-arc graphs. In this
dissertation, we show that the efficient domination problem is
NP-complete when restricted to planar bipartite graphs, the line
graphs of planar bipartite graphs and chordal bipartite graphs.
For the weighted efficient domination problem, we present an O(
|V|) time algorithm on bipartite permutation graphs,an O(|V|+|E''
|) time algorithm on permutation graphs, an O(|V|loglog|V|+|E''|)
time algorithm on trapezoid graphs and an O(|V|) time algorithm
on distance-hereditary graphs,where |E''| denotes the number of
edges in the complement of G.On the other hand, we also
investigate the algorithmic complexity of the edge version
problem of efficient domination in graphs. The efficient edge
domination problem on general graphs has been shown to be NP-
complete, but can be solved in linear time when restricted to
generalized series-parallel graphs and interval graphs. As to
the weighted version of this problem, few work has been
published. In this dissertation, we prove that the efficient
edge domination problem is NP-complete when restricted to planar
bipartite graphs and hence it remains NP-complete on any
superclass of planar bipartite graphs, e.g., planar graphs and
bipartite graphs. In addition, we present O(|V|+|E|) time
algorithms to solve the weighted efficient edge domination
problem on bipartite permutation graphs, generalized series-
parallel graphs and chordal graphs. It is worth mentioning that
on chordal graphs, the weighted efficient domination problem is
NP-complete, but the weighted efficient edge domination is
linear time solvable.
Cover
Acknowledgments
Abstract
Contents
List of Tables
List of Figures
Chapter 1 Introduction
Chapter 2 The Classes of Graphs Studied in This Dissertation
2.1 Permutation Graphs
2.2 Trapezoid Graphs
2.3 Chordal Graphs
2.4 Bipartite Permutation Graphs
2.5 Chordal Bipartite Graphs
2.6 Distance-Hereditary Graphs
2.7 Generalized Series-Parallel Graphs
2.8 Containment Relations among Graph Classes
Chapter 3 Other Problems Equivalent to Efficient Domination
3.1 Perfect 1-Code Problem
3.2 Independent Perfect Domination Problem
3.3 Perfect 1-Domination Problem
Chapter 4 Algorithmic Results on Weighted Efficient Domination
4.1 NP-Completeness of Efficient Domination
4.2 An O(│V│) Time Algorithm on Bipartite Permutation Graphs
4.3 An O(│V│+│E│) Time Algorithm on Permutation Graphs
4.4 An O(│V│loglog│V│+│E│) Time Algorithm on Trapezoid Graphs
4.5 An O(│V│) Time Algorthm on Distance-Hereditary Graphs
Chapter 5 Algorithmic Results on Weighted Efficient Edge Domination
5.1 NP-Complereness of Efficient Edge Domination
5.2 An O(│V│+│E│) Time Algorithm on Bipartite Permutation Graphs
5.3 An O(│V│+│E│) Time Algorithm on Generalized Series-Parallel Graphs
5.4 An O(│V│+│E│) Time Algorithm on Chordal Graphs
Chapter 6 Conclusion and Future Works
Bibliography
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top