Independent Sets in Circular-Arc Graphs

DOI10.1006/JAGM.1995.1031zbMATH Open0839.68069OpenAlexW2032853328MaRDI QIDQ4845846FDOQ4845846

Authors:

Publication date: 28 May 1996

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1995.1031

Recommendations

• A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
• scientific article; zbMATH DE number 140476
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Linear time algorithms on circular-arc graphs
• scientific article; zbMATH DE number 4215389

zbMATH Keywords

linear time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (14)

• Algorithms for clique-independent sets on subclasses of circular-arc graphs
• Polynomial time algorithms on circular-arc overlap graphs
• Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
• A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Stability in circular arc graphs
• Irredundancy in circular arc graphs
• Temporal interval cliques and independent sets
• Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals
• Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
• Linear time algorithms on circular-arc graphs
• Circular permutation graph family with applications
• Maximum weight independent set of circular-arc graph and its application
• A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone

This page was built for publication: Independent Sets in Circular-Arc Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4845846)