Labelled packing functions in graphs

DOI10.1016/J.IPL.2019.105863MaRDI QIDQ2011027zbMATH OpenOpenAlexWikidataFDO

Authors E. Hinrichsen, V. Leoni, Martín D. Safe

Publication date 28 November 2019

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2019.105863

zbMATH Keywords

computational complexitystrongly chordal graphlinear-time algorithmclique independencelabelled packing problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• $$\{k\}$$-Packing Functions of Graphs
• On the complexity of the {\(k\)}-packing function problem
• Towards a polynomial equivalence between \(\{k\}\)-packing functions and \(k\)-limited packings in graphs
• The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs
• NP-completeness of the \(\{k \}\)-packing function problem in graphs

Cites work

• scientific article; zbMATH DE number 1420904 (Why is no real title available?)
• $$\{k\}$$-Packing Functions of Graphs
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Algorithmic Aspects of Neighborhood Numbers
• Algorithmic aspects of clique-transversal and clique-independent sets
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Characterizations of strongly chordal graphs
• Generalized limited packings of some graphs with a limited number of \(P_4\)-partners
• Limited packing and multiple domination problems: polynomial time reductions
• Limited packings in graphs
• On 2-limited packings of complete grid graphs
• On the complexity of the {\(k\)}-packing function problem
• The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs
• The multiple domination and limited packing problems in graphs
• Variations of \(Y\)-dominating functions on graphs

Cited in

(5)

• $$\{k\}$$-Packing Functions of Graphs
• On the complexity of the {\(k\)}-packing function problem
• Towards a polynomial equivalence between \(\{k\}\)-packing functions and \(k\)-limited packings in graphs
• NP-completeness of the \(\{k \}\)-packing function problem in graphs
• Pak-Stanley labeling for central graphical arrangements

This page was built for publication: Labelled packing functions in graphs

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