查詢結果分析
來源資料
相關文獻
- A Branch-and-bound Algorithm for the k-cut Problem
- 都市計畫草圖替選方案分析模式之實例研究
- Minimum AFI for CSP-1 Plan Based on Fuzzy Optimization
- 以配銷需求規劃(DRP)為核心之配銷管理模式
- 臺灣地區花卉最適運銷量之決定:兼論採行遠端拍賣之可行性
- Bayesian Average Outgoing Quality Limit Sampling Plans Based on Fuzzy Optimization
- 以電子試算表建立配送車隊數量指派模式之研究
- 產能衝刺階段電子元件廠投料數學規劃模式之實例應用
- 多目標決策分析技術應用於遊憩設施區位設置
- 三維克希荷夫重合前深度移位
頁籤選單縮合
題名 | A Branch-and-bound Algorithm for the k-cut Problem=k-cut問題之分支界限演算法 |
---|---|
作者 | 葉維彰; | 書刊名 | 逢甲學報 |
卷期 | 38 2000.12[民89.12] |
頁次 | 頁89-94 |
分類號 | 440.11 |
關鍵詞 | 圖形理論; K-cut問題; 數學規劃; 分支界限演算法; Graph theory; NP-hard; K-cut problem; Mathematical programming; Branch-and-bound; |
語文 | 英文(English) |
中文摘要 | 本研究所要討論之主題是屬於圖形分割問題,為將圖形分割使各分割後之子圖形中的節點數或相關邊的權值,按照某給定之特點準則而最佳化。k-cut問題為複雜難解的NP-hard問題,然其應用卻非常實際,包括平行電腦系統通訊成本之最小化、叢集問題、VLSI之設計與網路可靠度等等。分支界限演算法常常用來解決NP-hard問題,其效率通常優於單純之窮舉法。於本研究中,我們不僅提出本問題之數學規劃模式,並率先發展一分支界限演算法以殺解決這些問題。 |
英文摘要 | The k-cut problem is a NP-hard generalization of the min-cut problem. It is to separate a weighted graph with k specified vertices into k components of unspecified size such that the total weight between components is minimized. In this paper, we develop an effective branch-and-bound algorithm to solve the k-cut problem. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。