A sequential algorithm for finding a maximum weight K-independent set on interval graphs

References

• Ahuja , R. K. , Mehlhorn , K. , Orlin , J. B. and Tarjan , R. E. 1990 . Faster algorithms for the shortest path problem . JACM , 37 : 213 – 223 .
   Google Scholar
• Edmonds , J. and Karp , R. M. 1972 . Theoretical improvements in algorithmic efficiency for network flow problems . JACM , 19 : 248 – 264 .
   Google Scholar
• Fulkerson , D. R. and Gross , O. A. 1965 . Incidence matrices and intervals graphs . Pacific J. Math. , 15 : 835 – 855 .
   Web of Science ®Google Scholar
• Garey , M. R. and Johnson , D. S. 1979 . Computer and Intractability: A Guide to the Theory of NP-Completeness , San Francisco, CA : Freeman .
   Google Scholar
• Gilmore , P. C. and Hoffman , A. J. 1964 . A characterization of Comparability graphs and of interval graphs . Canad. J. Math. , 16 : 539 – 548 .
   Web of Science ®Google Scholar
• Golumbic , M. C. 1980 . Algorithmic Graph Theory and Perfect Graphs , New York : Academic Press .
   Google Scholar
• Hsiao , J. Y. , Tang , C. Y. and Chang , R. S. 1991 . Solving the single step graph searching problem by solving the maximum two-independent set problem . Information Processing Letters , 40 : 283 – 287 .
   Google Scholar
• Hsiao , J. Y. , Tang , C. Y. and Chang , R. S. 1992 . An efficient algorithm for finding a maximum weight 2-independent set on interval graphs . Information Processing Letters , 43 : 229 – 235 .
   Web of Science ®Google Scholar
• Hsu , W. L. and Tsai , K. H. 1989 . Proceedings of 27th Allerton Conf. on Communication, Control and Computing . A linear time algorithm for the two-track assignment problem . 1989 . pp. 291 – 300 .
   Google Scholar
• Johnson , D. S. 1985 . The NP-Completeness Column: An on going guide . J. Algorithms , 6 434 – 451 .
   Web of Science ®Google Scholar
• Lou , R. D. , Sarrafgadeh , M. and Lee , D. T. 1992 . An optimal algorithm for the maximum two-chain problem . SIAM J. Discrete Math. , 5 285 – 304 .
   Google Scholar
• Roberts , F. S. 1978 . Graph Theory and its Application to Problems of Society , Philadelphia, PA : SIAM .
   Google Scholar
• Sarrafgadeh , M. and Lee , D. T. 1989 . A new approach to topological via minimization . IEEE Trans. Computer Aided Design , 8 : 890 – 900 .
   Google Scholar
• Yannakakis , M. and Gavril , F. 1987 . The maximum k-colorable subgraph problem for chordal graphs . Information Processing Letters , 24 : 133 – 137 .
   Google Scholar