Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs

1984/03/01 by Joseph Y.‐T. Leung, Joseph Y.-T Leung · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithm #Arc (geometry) #Chordal graph #Combinatorics #Discrete mathematics #Geometry #Graph #Graph Labeling and Dimension Problems #Indifference graph #Interval (graph theory) #Interval graph #Limits and Structures in Graph Theory #Line graph #Mathematics #Maximal independent set #Pathwidth #Split graph

paper · doi:10.1016/0196-6774(84)90037-3

crossref issued 1984/03/01 · crossref published 1984/03/01 · crossref published-print 1984/03/01 · openalex publication_date 1984/03/01 · crossref created 2005/02/10 · crossref deposited 2019/01/29 · openalex created_date 2025/10/10 · crossref indexed 2025/10/12 · openalex updated_date 2025/11/06

Citations

• Representation of a finite graph by a set of intervals on the real line
• On maximal independent sets of vertices in claw-free graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On rigid circuit graphs
• Efficient algorithms for interval graphs and circular‐arc graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Algorithmic Aspects of Vertex Elimination on Graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Incidence matrices and interval graphs

Cited by

• Maximal independent set [wikipedia]