National Changhua University of Education Institutional Repository : Item 987654321/9975

English | 正體中文 | 简体中文 | Items with full text/Total items : 6507/11669
Visitors : 30083140 Online Users : 786

RC Version 3.2 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

Scope Adv. Search

Login ‧ Upload ‧ Help ‧ About ‧ Administer

NCUEIR > College of Engineering > Department and Graduate Institute of Computer Science and Information Engineering > Periodical Articles > Item 987654321/9975

Please use this identifier to cite or link to this item: http://ir.ncue.edu.tw/ir/handle/987654321/9975

Title:	An efficient algorithm for finding a maximum weight two-independent set on interval graphs
Authors:	Hsiao, Ju-Yuan;Tang, C. Y.;Chang, R. S.
Contributors:	資訊工程系
Keywords:	Analysis of algorithms;Combinatorial problems;Design of algorithms
Date:	1992-10
Issue Date:	2012-05-02T09:36:37Z
Publisher:	Elsevier BV
Abstract:	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.
Relation:	Information Processing Letters, 43(5): 229-235
Appears in Collections:	[Department and Graduate Institute of Computer Science and Information Engineering] Periodical Articles

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	733	View/Open