TY - GEN

T1 - On the problem of finding all maximum weight independent sets in intervaland circular-arc graphs

AU - Liang, Y. D.

AU - Dhall, S. K.

AU - Lakshmivarahan, S.

N1 - Publisher Copyright:
© 1991 IEEE.

PY - 1991

Y1 - 1991

N2 - Leung (J. Algorithms, 5 (1984)) presented algorithms for generating all the maximal independent sets in interval graphs and circular-arc graphs. The algorithms take O (n2+p) steps, where β is the sum of the number of nodes in all maximal independent sets. In this paper we use a new technique to give fast and efficient algorithms for finding all the maximum weight independent sets in interval graphs and circular-arc graphs. Our algorithms take 0(max(n2,β)) steps in 0(n2) space, where β is the sum of the number of nodes in all maximum weight independent sets. Our algorithms can be directly applied for finding a maximum weight independent set in these graphs in O (n2) steps. Thus, our result is an improvement over the best known result of 0(n2logn) [4, 6] for finding the maximum weight independent set in circular-arc graphs.

AB - Leung (J. Algorithms, 5 (1984)) presented algorithms for generating all the maximal independent sets in interval graphs and circular-arc graphs. The algorithms take O (n2+p) steps, where β is the sum of the number of nodes in all maximal independent sets. In this paper we use a new technique to give fast and efficient algorithms for finding all the maximum weight independent sets in interval graphs and circular-arc graphs. Our algorithms take 0(max(n2,β)) steps in 0(n2) space, where β is the sum of the number of nodes in all maximum weight independent sets. Our algorithms can be directly applied for finding a maximum weight independent set in these graphs in O (n2) steps. Thus, our result is an improvement over the best known result of 0(n2logn) [4, 6] for finding the maximum weight independent set in circular-arc graphs.

UR - http://www.scopus.com/inward/record.url?scp=33746347889&partnerID=8YFLogxK

U2 - 10.1109/SOAC.1991.143921

DO - 10.1109/SOAC.1991.143921

M3 - Conference article

AN - SCOPUS:33746347889

T3 - Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991

SP - 465

EP - 470

BT - Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1991 Symposium on Applied Computing, SOAC 1991

Y2 - 3 April 1991 through 5 April 1991

ER -