Algorithmic Aspects of Neighborhood Numbers

DOI10.1137/0406002MaRDI QIDQ5285934zbMATH OpenOpenAlexFDO

Authors Martin Farber, Zsolt Tuza, Gerard Jennhwa Chang

Publication date 29 June 1993

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/1fad736bcfdcdd52974b4e6bfba8fafdcc315c40

zbMATH Keywords

chordal graphsclique-independence problemclique-transversal problemneighbourhood covering problemneighbourhood independence problemNP-complete

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• k-Neighborhood-Covering and -Independence Problems for Chordal Graphs
• scientific article; zbMATH DE number 29793
• scientific article; zbMATH DE number 89406
• Neighborhood covering and independence on P₄-tidy graphs and tree-cographs
• Neighborhood perfect graphs

Cited in

(38)

• Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Approximating weighted neighborhood independent sets
• A clique tree algorithm for partitioning a chordal graph into transitive subgraphs
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
• Algorithmic aspects of clique-transversal and clique-independent sets
• Labelled packing functions in graphs
• Complete-subgraph-transversal-sets problem on bounded treewidth graphs
• Neighborhood covering and independence on P₄-tidy graphs and tree-cographs
• On some graph classes related to perfect graphs: a survey
• The clique-perfectness and clique-coloring of outer-planar graphs
• Approximation algorithms for clique transversals on some graph classes
• Variations of maximum-clique transversal sets on graphs
• Clique-transversal sets and clique-coloring in planar graphs
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Distance-hereditary graphs are clique-perfect
• Algorithms for clique-independent sets on subclasses of circular-arc graphs
• Clique-perfectness and balancedness of some graph classes
• The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs
• scientific article; zbMATH DE number 29793 (Why is no real title available?)
• Weighted maximum-clique transversal sets of graphs
• k-Neighborhood-Covering and -Independence Problems for Chordal Graphs
• scientific article; zbMATH DE number 7051199 (Why is no real title available?)
• The clique-transversal set problem in claw-free graphs with degree at most 4
• An Optimal Algorithm to Solve 2-Neighbourhood Covering Problem on Interval Graphs
• Minimum r-neighborhood covering set of permutation graphs
• Clique-perfectness of claw-free planar graphs
• Clique-transversal number of graphs whose clique-graphs are trees
• The k-neighbourhood-covering problem on interval graphs
• Clique-perfectness of complements of line graphs
• Upper Clique Transversals in Graphs
• Conformality of minimal transversals of maximal cliques
• Conformal hypergraphs: duality and implications for the upper clique transversal problem
• Minimum clique bicoloring
• Algorithms for finding clique-transversals of graphs
• Variations of \(Y\)-dominating functions on graphs
• Bounds on the clique-transversal number of regular graphs

This page was built for publication: Algorithmic Aspects of Neighborhood Numbers

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