AN EFFICIENT ALGORITHM FOR FINDING A MAXIMUM WEIGHT INDEPENDENT SET OF A CIRCLE GRAPH

Authors
GOLDSCHMIDT O TAKVORIAN A
Citation
O. Goldschmidt et A. Takvorian, AN EFFICIENT ALGORITHM FOR FINDING A MAXIMUM WEIGHT INDEPENDENT SET OF A CIRCLE GRAPH, IEICE transactions on fundamentals of electronics, communications and computer science, E77A(10), 1994, pp. 1672-1674
Citations number
NO
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
Journal title
IEICE transactions on fundamentals of electronics, communications and computer science → ACNP
ISSN journal
09168508
Volume
E77A
Issue
10
Year of publication
1994
Pages
1672 - 1674
Database
ISI
SICI code
0916-8508(1994)E77A:10<1672:AEAFFA>2.0.ZU;2-#
Abstract
We present an O(nN) time and O(n2) space algorithm for finding a maxim um weight independent set of a circle (or overlap) graph of n chords ( or intervals) on N endpoints, based on an alternative definition of su ch graphs. The results improve on the best previously known algorithms for this case.