An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs |
| |
| Authors: | Mrinmoy Hota Madhumangal Pal Tapan K Pal |
| |
| Institution: | (1) Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore, 721 102, India;(2) Department of Mathematics, Midnapore College, Midnapore, 721 101, India |
| |
| Abstract: | The maximum weight k-independent set problem has applications in many practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design layout and routing problem. Based on DAG (Directed Acyclic Graph) approach, an O(kn
2) time sequential algorithm is designed in this paper to solve the maximum weight k-independent set problem on weighted trapezoid graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph. |
| |
| Keywords: | trapezoid graph independent set path network flow problem combinatorial problems design of algorithms analysis of algorithms |
| 本文献已被 SpringerLink 等数据库收录！ |
|
