Labelled packing functions in graphs

DOI10.1016/J.IPL.2019.105863zbMATH Open1481.05127OpenAlexW2984247531WikidataQ126867033 ScholiaQ126867033MaRDI QIDQ2011027FDOQ2011027

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

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

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)

Cites Work

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

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)