Algorithmic Aspects of Neighborhood Numbers

DOI10.1137/0406002zbMATH Open0777.05085OpenAlexW2012550027MaRDI QIDQ5285934FDOQ5285934

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

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_4\)-tidy graphs and tree-cographs
• Neighborhood perfect graphs

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)

Cited In (33)

• 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
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• A clique tree algorithm for partitioning a chordal graph into transitive subgraphs
• Title not available (Why is that?)
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• An Optimal Algorithm to Solve 2-Neighbourhood Covering Problem on Interval Graphs
• The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs
• Clique-transversal number of graphs whose clique-graphs are trees
• The clique-transversal set problem in claw-free graphs with degree at most 4
• Approximating weighted neighborhood independent sets
• Neighborhood covering and independence on \(P_4\)-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
• Approximation algorithms for clique-transversal sets and clique-independent sets in cubic 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)