National Changhua University of Education Institutional Repository : Item 987654321/9975
English  |  正體中文  |  简体中文  |  全文筆數/總筆數 : 6507/11669
造訪人次 : 30041061      線上人數 : 486
RC Version 3.2 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜尋範圍 進階搜尋

請使用永久網址來引用或連結此文件: http://ir.ncue.edu.tw/ir/handle/987654321/9975

題名: An efficient algorithm for finding a maximum weight two-independent set on interval graphs
作者: Hsiao, Ju-Yuan;Tang, C. Y.;Chang, R. S.
貢獻者: 資訊工程系
關鍵詞: Analysis of algorithms;Combinatorial problems;Design of algorithms
日期: 1992-10
上傳時間: 2012-05-02T09:36:37Z
出版者: Elsevier BV
摘要: In this paper, we introduce an O(n) time algorithm to solve the maximum weight independent set problem on an interval graph with n vertices given its interval representation with sorted endpoints list. Based on this linear algorithm, we design an O(n2) time algorithm using O(n2) space to solve the maximum weight 2-independent set problem on an interval graph with n vertices. With a slight extension and modification of our algorithm, the maximum weight k-independent set problem on an interval graph with n vertices can be solved in O(nk) time using O(nk) space.
關聯: Information Processing Letters, 43(5): 229-235
顯示於類別:[資訊工程學系] 期刊論文

文件中的檔案:

檔案 大小格式瀏覽次數
index.html0KbHTML732檢視/開啟


在NCUEIR中所有的資料項目都受到原著作權保護.

 

DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回饋