On the vertex packing problem

DOI10.1007/BF01195324MaRDI QIDQ2366214zbMATH OpenOpenAlexFDO

Authors Yanyan Li, Caterina De Simone

Publication date 29 June 1993

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01195324

zbMATH Keywords

subgraphs characterizationvertex packing problem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A nice class for the vertex packing problem
• scientific article; zbMATH DE number 3976364
• scientific article; zbMATH DE number 434914
• Efficient subgraphs packing

Cites work

• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Bull-free Berge graphs are perfect
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Matching theory
• On a property of the class of n-colorable graphs
• On maximal independent sets of vertices in claw-free graphs
• Some simplified NP-complete graph problems
• Stability number of bull- and chair-free graphs
• The struction of a graph: Application to CN-free graphs

Cited in

(28)

• Relaxations of vertex packing
• Stability number of bull- and chair-free graphs
• New classes of Berge perfect graphs
• Complexity of list coloring problems with a fixed total number of colors
• A nice class for the vertex packing problem
• On the use of Boolean methods for the computation of the stability number
• Independent domination in finitely defined classes of graphs
• Stability number of bull- and chair-free graphs revisited
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• A class of web-based facets for the generalized vertex packing problem
• Extension of hereditary classes with substitutions
• Algorithm for the vertex packing problem
• Independent domination in finitely defined classes of graphs: polynomial algorithms
• Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
• A finiteness theorem for primal extensions
• Bounding the clique-width of H-free chordal graphs
• scientific article; zbMATH DE number 434914 (Why is no real title available?)
• The Maximum Independent Set Problem in Planar Graphs
• scientific article; zbMATH DE number 3943843 (Why is no real title available?)
• scientific article; zbMATH DE number 3976364 (Why is no real title available?)
• scientific article; zbMATH DE number 1960287 (Why is no real title available?)
• On the structure of (pan, even hole)-free graphs
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• The mixed vertex packing problem.
• Portfolio optimization through a network approach: network assortative mixing and portfolio diversification
• On independent vertex sets in subclasses of apple-free graphs
• All minimal prime extensions of hereditary classes of graphs
• New applications of clique separator decomposition for the maximum weight stable set problem

This page was built for publication: On the vertex packing problem

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