Weighted maximum-clique transversal sets of graphs

DOI10.5402/2011/540834zbMath1237.05153OpenAlexW2049038982WikidataQ58689694 ScholiaQ58689694MaRDI QIDQ410660

Chuan-Min Lee

Publication date: 3 April 2012

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

Full work available at URL: https://doi.org/10.5402/2011/540834

zbMATH Keywords

distance-hereditary graphssplit graphscomparability graphsbalanced graphsstrongly chordal graphHelly circular-arc graphsgraphs of bounded treewidth

Mathematics Subject Classification ID

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

Related Items (2)

Inapproximability of $H$-Transversal/Packing ⋮ Parameterized complexity of computing maximum minimal blocking and hitting sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum \(h\)-colourable subgraph problem in balanced graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Clique-transversal sets of line graphs and complements of line graphs
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Algorithms for finding clique-transversals of graphs
• Characterizations of strongly chordal graphs
• Distance-hereditary graphs
• Covering the cliques of a graph with vertices
• Modular decomposition and transitive orientation
• Treewidth. Computations and approximations
• On the clique-transversal number of chordal graphs
• On clique-transversals and clique-independent sets
• On covering all cliques of a chordal graph
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Algorithmic aspects of clique-transversal and clique-independent sets
• Doubly lexical ordering of dense 0--1 matrices
• The algorithmic complexity of the minus clique-transversal problem
• Variations of maximum-clique transversal sets on graphs
• Distance-hereditary graphs are clique-perfect
• Algorithms for clique-independent sets on subclasses of circular-arc graphs
• Triangulated graphs and the elimination process
• On balanced graphs
• Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
• Maximal Flow Through a Network
• On cliques of Helly Circular-arc Graphs
• Three Partition Refinement Algorithms
• A new approach to the maximum-flow problem
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Graph Classes: A Survey
• The Pathwidth and Treewidth of Cographs
• Algorithmic Aspects of Neighborhood Numbers
• Algorithm Theory - SWAT 2004
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Weighted maximum-clique transversal sets of graphs