Maximum weight independent set of circular-arc graph and its application

DOI10.1007/BF02832044zbMath1107.68067OpenAlexW2092132110MaRDI QIDQ861467

Swagata Mandal, Madhumangal Pal

Publication date: 29 January 2007

Published in: Journal of Applied Mathematics and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02832044

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Robust maximum weighted independent-set problems on interval graphs ⋮ \(L(2,1)\)-labeling of interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Parallel batched planar point location on the CCC
• An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
• Linear time algorithms on circular-arc graphs
• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle 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
• Algorithms on circular-arc graphs
• An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs

This page was built for publication: Maximum weight independent set of circular-arc graph and its application