2002/12/10 by Yan Liang, Sudarshan Dhall, S. Lakshmivarahan · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph Labeling and Dimension Problems #Combinatorics #Maximal independent set #Mathematics #Independent set #Interval (graph theory) #Interval graph #Discrete mathematics #Arc (geometry) #Set (abstract data type) #Algorithm #Pathwidth #Computer science #Graph #Line graph
paper · doi:10.1109/soac.1991.143921
openalex publication_date 2002/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
J.Y.-T. Leung (J. Algorithms, no.5, (1984)) presented algorithms for generating all the maximal independent sets in interval graphs and circular-arc graphs. The algorithms take O(n/sup 2/+ beta ) steps, where beta is the sum of the number of nodes in all maximal independent sets. The authors 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. The algorithms take O(max(n/sup 2/, beta )) steps in O(n/sup 2/) space, where beta is the sum of the number of nodes in all maximum weight independent sets. The algorithms can be directly applied for finding a maximum weight independent set in these graphs in O(n/sup 2/) steps. Thus, the result is an improvement over the best known result of O(n/sup 2/ log n) for finding the maximum weight independent set in circular-arc graphs.>