Covering, Packing and Generalized Perfection

DOI10.1137/0606012MaRDI QIDQ3220635zbMATH OpenOpenAlexFDO

Authors G. L. Nemhauser, Gerard Jennhwa Chang

Publication date 1985

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0606012

zbMATH Keywords

chordal graphscoveringindependencepackingperfect graphsstability

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)

Recommendations

• On packing and covering numbers of graphs
• On relation between packing and covering number of graphs.
• Covering all cliques of a graph
• Packing and covering a tree by subtrees
• scientific article; zbMATH DE number 4089565

Cites work

• R -Domination in Graphs
• A linear algorithm for the domination number of a tree
• Algorithmic Aspects of Vertex Elimination on Graphs
• Balanced matrices
• scientific article; zbMATH DE number 3152801 (Why is no real title available?)
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3503127 (Why is no real title available?)
• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Normal hypergraphs and the perfect graph conjecture
• On the perfect graph conjecture
• Relations between packing and covering numbers of a tree
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs

Cited in

(13)

• Labeling algorithms for domination problems in sun-free chordal graphs
• Total domination in block graphs
• Centers of chordal graphs
• On packing and covering numbers of graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• A brief survey of perfect Mendelsohn packing and covering designs
• On edge perfectness and classes of bipartite graphs
• Optimization problems in multiple subtree graphs
• On relation between packing and covering number of graphs.
• The ideal view on Rackoff's coverability technique
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Generalising Fisher's inequality to coverings and packings
• Bibliography on domination in graphs and some basic definitions of domination parameters

This page was built for publication: Covering, Packing and Generalized Perfection

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