Algorithmic aspects of clique-transversal and clique-independent sets

DOI10.1016/S0166-218X(99)00159-6zbMath0948.68135OpenAlexW2021102038MaRDI QIDQ1971220

Venkatesan Guruswami, C. Pandu Rangan

Publication date: 30 November 2000

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00159-6

zbMATH Keywords

minimum clique-transversal set

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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (44)

NP-hardness of the recognition of coordinated graphs ⋮ The algorithmic complexity of the minus clique-transversal problem ⋮ The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs ⋮ Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths ⋮ Clique-transversal number of graphs whose clique-graphs are trees ⋮ Clique-perfectness and balancedness of some graph classes ⋮ Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs ⋮ Approximating weighted neighborhood independent sets ⋮ On some graph classes related to perfect graphs: a survey ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Weighted maximum-clique transversal sets of graphs ⋮ Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs ⋮ Variations of maximum-clique transversal sets on graphs ⋮ Balanced matrices ⋮ Clique-transversal sets and clique-coloring in planar graphs ⋮ The clique-transversal set problem in claw-free graphs with degree at most 4 ⋮ Algorithms for finding clique-transversals of graphs ⋮ Variations of \(Y\)-dominating functions on graphs ⋮ Bounds on the clique-transversal number of regular graphs ⋮ Clique-perfectness of claw-free planar graphs ⋮ The geodesic-transversal problem ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs ⋮ Labelled packing functions in graphs ⋮ Distance-hereditary graphs are clique-perfect ⋮ Signed and minus clique-transversal functions on graphs ⋮ Clique-perfectness of complements of line graphs ⋮ Algorithms for clique-independent sets on subclasses of circular-arc graphs ⋮ Signed clique-transversal functions in graphs ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ The \(\langle t \rangle \)-property of some classes of graphs ⋮ Complete-subgraph-transversal-sets problem on bounded treewidth graphs ⋮ Partial characterizations of coordinated graphs: Line graphs and complements of forests ⋮ Clique-perfectness of complements of line graphs ⋮ Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs ⋮ Unnamed Item ⋮ The clique-perfectness and clique-coloring of outer-planar graphs ⋮ On balanced graphs ⋮ 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
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Clique-transversal sets of line graphs and complements of line graphs
• Characterizations of strongly chordal graphs
• Neighborhood perfect graphs
• Chains, antichains, and fibres
• The maximum k-colorable subgraph problem for chordal graphs
• A unified approach to domination problems on interval graphs
• Covering all cliques of a graph
• Fibres and ordered set coloring
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of generalized clique covering
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Minimum Edge Dominating Sets
• Totally-Balanced and Greedy Matrices
• A Linear Recognition Algorithm for Cographs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Edge Dominating Sets in Graphs
• Edge-Deletion Problems
• Algorithms on circular-arc graphs
• Algorithmic Aspects of Neighborhood Numbers

This page was built for publication: Algorithmic aspects of clique-transversal and clique-independent sets