Algorithmic Aspects of Neighborhood Numbers

DOI10.1137/0406002zbMath0777.05085OpenAlexW2012550027MaRDI QIDQ5285934

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

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

Related Items

An Optimal Algorithm to Solve 2-Neighbourhood Covering Problem on Interval Graphs, A clique tree algorithm for partitioning a chordal graph into transitive subgraphs, The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs, Clique-transversal number of graphs whose clique-graphs are trees, Clique-perfectness and balancedness of some graph classes, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs, Approximating weighted neighborhood independent sets, On some graph classes related to perfect graphs: a survey, Weighted maximum-clique transversal sets of graphs, Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs, Variations of maximum-clique transversal sets on graphs, Clique-transversal sets and clique-coloring in planar 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, Clique-perfectness of claw-free planar graphs, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Labelled packing functions in graphs, Distance-hereditary graphs are clique-perfect, Thek-neighbourhood-covering problem on interval graphs, Algorithms for clique-independent sets on subclasses of circular-arc graphs, Complete-subgraph-transversal-sets problem on bounded treewidth graphs, Clique-perfectness of complements of line graphs, Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs, The clique-perfectness and clique-coloring of outer-planar graphs, Approximation algorithms for clique transversals on some graph classes, Minimum r-neighborhood covering set of permutation graphs