Algorithms for clique-independent sets on subclasses of circular-arc graphs

DOI10.1016/J.DAM.2006.03.022MaRDI QIDQ2500526zbMATH OpenOpenAlexFDO

Authors Guillermo Durán, Min Chih Lin, Sergio Mera, Jayme L. Szwarcfiter

Publication date 17 August 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.03.022

zbMATH Keywords

Helly circular-arc graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Independent Sets in Circular-Arc Graphs
• New clique and independent set algorithms for circle graphs
• On cliques of Helly Circular-arc Graphs
• Linear time algorithms on circular-arc graphs
• A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 2188345 (Why is no real title available?)
• Algorithmic Aspects of Neighborhood Numbers
• Algorithmic aspects of clique-transversal and clique-independent sets
• Algorithms on circular-arc graphs
• An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
• An Efficient Test for Circular-Arc Graphs
• Characterizing circular-arc graphs
• Efficient graph representations
• Fibres and ordered set coloring
• Linear time algorithms on circular-arc graphs
• Linear-time recognition of circular-arc graphs
• Maximum \(h\)-colourable subgraph problem in balanced graphs
• On balanced graphs
• On clique-transversals and clique-independent sets
• Self-clique Helly circular-arc graphs
• Stability in circular arc graphs

Cited in

(11)

• On cliques of Helly Circular-arc Graphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• On some graph classes related to perfect graphs: a survey
• Algorithms for finding clique-transversals of graphs
• Weighted maximum-clique transversal sets of graphs
• Clique-perfectness and balancedness of some graph classes
• Clique-perfectness of complements of line graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• The clique operator on circular-arc graphs
• Variations of maximum-clique transversal sets on graphs
• Efficient and perfect domination on circular-arc graphs

This page was built for publication: Algorithms for clique-independent sets on subclasses of circular-arc graphs

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