Algorithmic aspects of clique-transversal and clique-independent sets

DOI10.1016/S0166-218X(99)00159-6MaRDI QIDQ1971220zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Algorithms for finding clique-transversals of graphs
• scientific article; zbMATH DE number 2044919
• On clique-transversals and clique-independent sets
• Approximation algorithms for clique transversals on some graph classes
• Weighted maximum-clique transversal sets of graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A unified approach to domination problems on interval graphs
• Algorithmic Aspects of Neighborhood Numbers
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Algorithms on circular-arc graphs
• Chains, antichains, and fibres
• Characterizations of strongly chordal graphs
• Clique-transversal sets of line graphs and complements of line graphs
• Covering all cliques of a graph
• Domination, independent domination, and duality in strongly chordal graphs
• Edge Dominating Sets in Graphs
• Edge-Deletion Problems
• Fibres and ordered set coloring
• Minimum Edge Dominating Sets
• Neighborhood perfect graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• The complexity of generalized clique covering
• The maximum k-colorable subgraph problem for chordal graphs
• Totally-Balanced and Greedy Matrices

Cited in

(46)

• scientific article; zbMATH DE number 2230915 (Why is no real title available?)
• The geodesic-transversal problem
• On some graph classes related to perfect graphs: a survey
• Bounds on the clique-transversal number of regular graphs
• The \(\langle t \rangle \)-property of some classes of graphs
• Clique-transversal sets and clique-coloring in planar graphs
• Complete-subgraph-transversal-sets problem on bounded treewidth graphs
• Clique-perfectness of complements of line graphs
• The clique-transversal set problem in claw-free graphs with degree at most 4
• The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Partial characterizations of coordinated graphs: Line graphs and complements of forests
• Upper Clique Transversals in Graphs
• Characterization and recognition of Helly circular-arc clique-perfect graphs
• Algorithms for clique-independent sets on subclasses of circular-arc graphs
• The algorithmic complexity of the minus clique-transversal problem
• Inapproximability of \(H\)-transversal/packing
• Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
• Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs
• Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
• Approximation algorithms for clique transversals on some graph classes
• 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
• Signed and minus clique-transversal functions on graphs
• Variations of \(Y\)-dominating functions on graphs
• Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
• Bounding the mim‐width of hereditary graph classes
• scientific article; zbMATH DE number 2230210 (Why is no real title available?)
• Approximating weighted neighborhood independent sets
• Clique-transversal number of graphs whose clique-graphs are trees
• Distance-hereditary graphs are clique-perfect
• Hitting all maximal independent sets of a bipartite graph
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• Variations of maximum-clique transversal sets on graphs
• Clique-perfectness of claw-free planar graphs
• Bounding the Mim-Width of Hereditary Graph Classes.
• Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
• On balanced graphs
• Signed clique-transversal functions in graphs
• The clique-perfectness and clique-coloring of outer-planar graphs
• Balanced matrices
• Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths
• Labelled packing functions in graphs
• NP-hardness of the recognition of coordinated graphs

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

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