An efficient algorithm for finding a maximum weight k-independent set on trapezoid graphs

Authors
Hota, M Pal, M Pal, TK
Citation
M. Hota et al., An efficient algorithm for finding a maximum weight k-independent set on trapezoid graphs, COMPUT OP A, 18(1), 2001, pp. 49-62
Citations number
18
Categorie Soggetti
Engineering Mathematics
Journal title
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
ISSN journal
09266003 → ACNP
Volume
18
Issue
1
Year of publication
2001
Pages
49 - 62
Database
ISI
SICI code
0926-6003(200101)18:1<49:AEAFFA>2.0.ZU;2-3
Abstract
The maximum weight k-independent set problem has applications in many pract ical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design layout and routing problem. Based on DAG (Directed Ac yclic Graph) approach, an O (kn(2)) time sequential algorithm is designed i n this paper to solve the maximum weight k-independent set problem on weigh ted trapezoid graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph.