Algorithms for finding clique-transversals of graphs
From MaRDI portal
Publication:940841
DOI10.1007/s10479-007-0189-xzbMath1163.90768OpenAlexW2094344015MaRDI QIDQ940841
Guillermo Durán, Sergio Mera, Min Chih Lin, Jayme Luiz Szwarcfiter
Publication date: 3 September 2008
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10533/139001
algorithmscircular-arc graphsHelly circular-arc graphs\(\overline{3K_{2}}\)-free circular-arc graphsclique-transversals
Related Items (13)
The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs ⋮ Clique-perfectness and balancedness of some graph classes ⋮ On some graph classes related to perfect graphs: a survey ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Weighted maximum-clique transversal sets of graphs ⋮ Variations of maximum-clique transversal sets on graphs ⋮ The clique-transversal set problem in claw-free graphs with degree at most 4 ⋮ Clique-perfectness of complements of line graphs ⋮ Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Approximation algorithms for clique transversals on some graph classes ⋮ Characterization and recognition of Helly circular-arc clique-perfect graphs ⋮ Hitting all maximal independent sets of a bipartite graph
Cites Work
- Unnamed Item
- Maximum \(h\)-colourable subgraph problem in balanced graphs
- Linear-time recognition of Helly circular-arc models and graphs
- Covering all cliques of a graph
- Linear time algorithms on circular-arc graphs
- Covering the cliques of a graph with vertices
- On clique-transversals and clique-independent sets
- Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
- Algorithmic aspects of clique-transversal and clique-independent sets
- Algorithms for clique-independent sets on subclasses of circular-arc graphs
- On balanced graphs
- Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Algorithms on circular-arc graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Algorithmic Aspects of Neighborhood Numbers
This page was built for publication: Algorithms for finding clique-transversals of graphs
