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

clique independencecomputational complexitylabelled packing problemlinear-time algorithmstrongly chordal graph

Mathematics Subject Classification ID

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

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

• $$\{k\}$$-Packing Functions of Graphs
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Algorithmic aspects of clique-transversal and clique-independent sets
• Algorithmic Aspects of Neighborhood Numbers
• 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
• scientific article; zbMATH DE number 1420904 (Why is no real title available?)
• 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)

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

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)