Covering, Packing and Generalized Perfection

DOI10.1137/0606012zbMath0556.05055OpenAlexW2055841009MaRDI QIDQ3220635

Nemhauser, George I., 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

independencestabilitycoveringpackingperfect graphschordal graphs

Mathematics Subject Classification ID

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

Related Items

On edge perfectness and classes of bipartite graphs, 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, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Counting clique trees and computing perfect elimination schemes in parallel, Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• A linear algorithm for the domination number of a tree
• Relations between packing and covering numbers of a tree
• On the perfect graph conjecture
• Normal hypergraphs and the perfect graph conjecture
• 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
• R -Domination in Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Balanced matrices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item