first
prev
toc
next
last
Download Citation
Recommend
Mark
Alert
Link
Print
Maximum weight k-independent set problem on permutation graphs
Authors:
Anita Saha a;
Madhumangal Pal a
| Affiliation: | a Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore, West Bengal, India |
DOI:
10.1080/00207160310001614972
Publication Frequency:
12 issues per year
Published in:
International Journal of Computer Mathematics,
Volume
80,
Issue
12
December
2003
, pages 1477
- 1487
International Journal of Computer Mathematics,
Volume
80,
Issue
12
December
2003
, pages 1477
- 1487
Subjects:
Analysis - Mathematics;
Bioinformatics;
Computer Mathematics;
Discrete Mathematics;
Mathematical Finance;
Mathematical Logic;
Mathematical Numerical Analysis;
Systems & Computer Architecture;
Number of References: 17
Formats available:
PDF
(English)
Article Requests:
Order Reprints
:
Request Permissions
-
Single Article Purchase:
US$37.00
-
buy now
-
Sign In
- Online Sample
add to cart 
[ show other buying options ]
View Article:
View Article (PDF)
Abstract
Based on a Directed Acyclic Graph approach, an O(kn2) time sequential algorithm is presented to solve the maximum weight k-independent set problem on weighted-permutation graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph. This problem has many applications in practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design and routing problem.
|
| Keywords: Permutation graph; Independent set; Network flow problem; Combinatorial problems; Design of algorithms; Analysis of algorithms |
| view references (17) |
|
Bookmark with:
|
CiteULike
Del.icio.us
BibSonomy
Connotea
More bookmarks
