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 graphsNP-completeclique-independence problemclique-transversal problemneighbourhood covering problemneighbourhood independence problem

Mathematics Subject Classification ID

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

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

(33)

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

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)