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

Y. D. Liang; S. K. Dhall; S. Lakshmivarahan

doi:10.1109/SOAC.1991.143921

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

Y. D. Liang, S. K. Dhall, S. Lakshmivarahan

Computer Science

University of Oklahoma

Research output: Contribution to book or proceeding › Conference article › peer-review

8 Scopus citations

Abstract

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 (n²+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(n²,β)) steps in 0(n²) 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 (n²) steps. Thus, our result is an improvement over the best known result of 0(n²logn) [4, 6] for finding the maximum weight independent set in circular-arc graphs.

Original language	English
Title of host publication	Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	465-470
Number of pages	6
ISBN (Electronic)	0818621362, 9780818621369
DOIs	https://doi.org/10.1109/SOAC.1991.143921
State	Published - 1991
Event	1991 Symposium on Applied Computing, SOAC 1991 - Kansas City, United States Duration: Apr 3 1991 → Apr 5 1991

Publication series

Name	Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991

Conference

Conference	1991 Symposium on Applied Computing, SOAC 1991
Country/Territory	United States
City	Kansas City
Period	04/3/91 → 04/5/91

Access to Document

10.1109/SOAC.1991.143921

Cite this

Liang, Y. D., Dhall, S. K., & Lakshmivarahan, S. (1991). On the problem of finding all maximum weight independent sets in intervaland circular-arc graphs. In Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991 (pp. 465-470). Article 143921 (Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SOAC.1991.143921

@inproceedings{9cb3cef660354bedaa36b2271c61ddc8,

title = "On the problem of finding all maximum weight independent sets in intervaland circular-arc graphs",

abstract = "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.",

author = "Liang, {Y. D.} and Dhall, {S. K.} and S. Lakshmivarahan",

note = "Publisher Copyright: {\textcopyright} 1991 IEEE.; 1991 Symposium on Applied Computing, SOAC 1991 ; Conference date: 03-04-1991 Through 05-04-1991",

year = "1991",

doi = "10.1109/SOAC.1991.143921",

language = "English",

series = "Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "465--470",

booktitle = "Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991",

address = "United States",

}

Liang, YD, Dhall, SK & Lakshmivarahan, S 1991, On the problem of finding all maximum weight independent sets in intervaland circular-arc graphs. in Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991., 143921, Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991, Institute of Electrical and Electronics Engineers Inc., pp. 465-470, 1991 Symposium on Applied Computing, SOAC 1991, Kansas City, United States, 04/3/91. https://doi.org/10.1109/SOAC.1991.143921

On the problem of finding all maximum weight independent sets in intervaland circular-arc graphs. / Liang, Y. D.; Dhall, S. K.; Lakshmivarahan, S.
Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991. Institute of Electrical and Electronics Engineers Inc., 1991. p. 465-470 143921 (Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991).

Research output: Contribution to book or proceeding › Conference article › peer-review

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.

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 -

Liang YD, Dhall SK, Lakshmivarahan S. On the problem of finding all maximum weight independent sets in intervaland circular-arc graphs. In Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991. Institute of Electrical and Electronics Engineers Inc. 1991. p. 465-470. 143921. (Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991). doi: 10.1109/SOAC.1991.143921

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this