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

DOI10.1002/net.10014zbMath0994.05142OpenAlexW2114616060MaRDI QIDQ4537611

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

independent setcircular-arc graph

Mathematics Subject Classification ID

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

Related Items (4)

Approximating minimum coloring and maximum independent set in dotted interval graphs ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach

Cites Work

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

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