A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone

DOI10.1002/NET.10014MaRDI QIDQ4537611zbMATH OpenOpenAlexFDO

Authors Glenn K. Manacher, Terrance A. Mankus

Publication date 1 July 2002

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.10014

zbMATH Keywords

circular-arc graphindependent set

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Independent Sets in Circular-Arc Graphs
• Finding maximum cliques on circular-arc graphs
• Linear time algorithms on circular-arc graphs
• AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs

Cites work

• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Efficient algorithms for interval graphs and circular-arc graphs
• Linear time algorithms on circular-arc graphs
• Stability in circular arc graphs

Cited in

(14)

• Finding a maximum set of independent chords in a circle
• Optimal parallel algorithms on circular-arc graphs
• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• Algorithms for clique-independent sets on subclasses of circular-arc graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Independent Sets in Circular-Arc Graphs
• Algorithms and Computation
• From a Circular-Arc Model to a Proper Circular-Arc Model
• Efficiently implementing maximum independent set algorithms on circle graphs
• Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs
• Approximating minimum coloring and maximum independent set in dotted interval graphs
• Maximum weight independent set of circular-arc graph and its application
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach

This page was built for publication: A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone

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