Algorithmic aspects of the generalized clique-transversal problem on chordal graphs

DOI10.1016/0166-218X(95)00048-VzbMath0854.68072MaRDI QIDQ1917287

Maw-Shang Chang, Jing-Ho Yan, Yi-Hua Chen, Gerard Jennhwa Chang

Publication date: 13 January 1997

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

zbMATH Keywords

chordal graphsclique transversal problem

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A linear-time algorithm for the weighted feedback vertex problem on interval graphs, The algorithmic complexity of the minus clique-transversal problem, The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs, Clique-transversal number of graphs whose clique-graphs are trees, Approximation results for the optimum cost chromatic partition problem, Weighted maximum-clique transversal sets of graphs, Variations of maximum-clique transversal sets on graphs, Algorithmic aspects of clique-transversal and clique-independent sets, 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, The geodesic-transversal problem, Labelled packing functions in graphs, Distance-hereditary graphs are clique-perfect, Signed and minus clique-transversal functions on graphs, Signed clique-transversal functions in graphs, Complete-subgraph-transversal-sets problem on bounded treewidth graphs

Cites Work

• Dominating sets for split and bipartite graphs
• Bibliography on domination in graphs and some basic definitions of domination parameters
• Clique-transversal sets of line graphs and complements of line graphs
• Characterizations of strongly chordal graphs
• The neighbourhood number of a graph
• \(K_ i\)-covers. I: Complexity and polytopes
• Neighborhood perfect graphs
• The maximum k-colorable subgraph problem for chordal graphs
• On chain and antichain families of a partially ordered set
• Covering all cliques of a graph
• Generalized vertex covering in interval graphs
• Covering the cliques of a graph with vertices
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• Some partitions associated with a partially ordered set
• A recognition algorithm for the intersection graphs of paths in trees
• The complexity of generalized clique covering
• Doubly lexical ordering of dense 0--1 matrices
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Representation of a finite graph by a set of intervals on the real line
• Totally-Balanced and Greedy Matrices
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Algorithms for maximumk-colorings andk-coverings of transitive graphs
• Three Partition Refinement Algorithms
• Edge-Deletion Problems
• Dominating Sets in Chordal Graphs
• Algorithmic Aspects of Neighborhood Numbers
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• The structure of Sperner k-families
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item