The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dans cet article, nous proposons un algorithme pour générer des ensembles indépendants de poids maximum dans un graphe circulaire, c'est-à-dire pour afficher tous les ensembles indépendants de poids maximum un par un sans duplication. La complexité temporelle est O(n3 + β ), où n est le nombre de sommets, la taille de sortie β, c'est-à-dire la somme des cardinalités des ensembles de sortie. Il est montré que la même approche peut être appliquée aux graphes en araignée et aux graphes de chevauchement en arc de cercle.
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.
Copier
Masakuni TAKI, Hirotaka HATAKENAKA, Toshinobu KASHIWABARA, "Algorithms for Generating Maximum Weight Independent Sets in Circle Graphs, Circular-Arc Overlap Graphs, and Spider Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 8, pp. 1636-1640, August 1999, doi: .
Abstract: In this paper we propose an algorithm for generating maximum weight independent sets in a circle graph, that is, for putting out all maximum weight independent sets one by one without duplication. The time complexity is O(n3 + β ), where n is the number of vertices, β output size, i. e. , the sum of the cardinalities of the output sets. It is shown that the same approach can be applied for spider graphs and for circular-arc overlap graphs.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_8_1636/_p
Copier
@ARTICLE{e82-a_8_1636,
author={Masakuni TAKI, Hirotaka HATAKENAKA, Toshinobu KASHIWABARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Algorithms for Generating Maximum Weight Independent Sets in Circle Graphs, Circular-Arc Overlap Graphs, and Spider Graphs},
year={1999},
volume={E82-A},
number={8},
pages={1636-1640},
abstract={In this paper we propose an algorithm for generating maximum weight independent sets in a circle graph, that is, for putting out all maximum weight independent sets one by one without duplication. The time complexity is O(n3 + β ), where n is the number of vertices, β output size, i. e. , the sum of the cardinalities of the output sets. It is shown that the same approach can be applied for spider graphs and for circular-arc overlap graphs.},
keywords={},
doi={},
ISSN={},
month={August},}
Copier
TY - JOUR
TI - Algorithms for Generating Maximum Weight Independent Sets in Circle Graphs, Circular-Arc Overlap Graphs, and Spider Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1636
EP - 1640
AU - Masakuni TAKI
AU - Hirotaka HATAKENAKA
AU - Toshinobu KASHIWABARA
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 1999
AB - In this paper we propose an algorithm for generating maximum weight independent sets in a circle graph, that is, for putting out all maximum weight independent sets one by one without duplication. The time complexity is O(n3 + β ), where n is the number of vertices, β output size, i. e. , the sum of the cardinalities of the output sets. It is shown that the same approach can be applied for spider graphs and for circular-arc overlap graphs.
ER -