An Efficient Algorithm for Finding a Maximum Weight Independent Set of a Circle Graph
Summary :
We present an O(nN) time and O(n2) space algorithm for finding a maximum weight independent set of a circle (or overlap) graph of n chords (or intervals) on N endpoints, based on an alternative definition of such graphs. The results improve on the best previously known algorithms for this case.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.10 pp.1672-1674
- Publication Date
- 1994/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithms, Data Structures and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Olivier GOLDSCHMIDT, Alexan TAKVORIAN, "An Efficient Algorithm for Finding a Maximum Weight Independent Set of a Circle Graph" in IEICE TRANSACTIONS on Fundamentals,
vol. E77-A, no. 10, pp. 1672-1674, October 1994, doi: .
Abstract: We present an O(nN) time and O(n2) space algorithm for finding a maximum weight independent set of a circle (or overlap) graph of n chords (or intervals) on N endpoints, based on an alternative definition of such graphs. The results improve on the best previously known algorithms for this case.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e77-a_10_1672/_p
Copy
@ARTICLE{e77-a_10_1672,
author={Olivier GOLDSCHMIDT, Alexan TAKVORIAN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Efficient Algorithm for Finding a Maximum Weight Independent Set of a Circle Graph},
year={1994},
volume={E77-A},
number={10},
pages={1672-1674},
abstract={We present an O(nN) time and O(n2) space algorithm for finding a maximum weight independent set of a circle (or overlap) graph of n chords (or intervals) on N endpoints, based on an alternative definition of such graphs. The results improve on the best previously known algorithms for this case.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - An Efficient Algorithm for Finding a Maximum Weight Independent Set of a Circle Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1672
EP - 1674
AU - Olivier GOLDSCHMIDT
AU - Alexan TAKVORIAN
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 1994
AB - We present an O(nN) time and O(n2) space algorithm for finding a maximum weight independent set of a circle (or overlap) graph of n chords (or intervals) on N endpoints, based on an alternative definition of such graphs. The results improve on the best previously known algorithms for this case.
ER -
English
