A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
From MaRDI portal
Publication:4537611
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
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
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
