Algorithmic aspects of broadcast independence

DOI10.1016/J.DAM.2022.03.001MaRDI QIDQ2127617zbMATH OpenOpenAlexFDO

Authors Dieter Rautenbach, Stéphane Bessy

Publication date 20 April 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.07248

zbMATH Keywords

broadcast independence number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)

Abstract: An independent broadcast on a connected graph $G$ is a function $f:V(G)omathbb{N}_0$ such that, for every vertex $x$ of $G$, the value $f(x)$ is at most the eccentricity of $x$ in $G$, and $f(x)>0$ implies that $f(y)=0$ for every vertex $y$ of $G$ within distance at most $f(x)$ from $x$. The broadcast independence number $alph{a}_b(G)$ of $G$ is the largest weight $sumlimit{s}_{xinV(G)}f(x)$ of an independent broadcast $f$ on $G$. We describe an efficient algorithm that determines the broadcast independence number of a given tree. Furthermore, we show NP-hardness of the broadcast independence number for planar graphs of maximum degree four, and hardness of approximation for general graphs. Our results solve problems posed by Dunbar, Erwin, Haynes, Hedetniemi, and Hedetniemi (2006), Hedetniemi (2006), and Ahmane, Bouchemakh, Sopena (2018).

Recommendations

• Relating broadcast independence and independence
• On the broadcast independence number of grid graph
• On the broadcast independence number of caterpillars
• Girth, minimum degree, independence, and broadcast independence
• Boundary independent broadcasts in graphs

Cites work

• scientific article; zbMATH DE number 2170461 (Why is no real title available?)
• A linear‐time algorithm for broadcast domination in a tree
• Broadcasts in graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On the broadcast independence number of caterpillars
• On the broadcast independence number of grid graph
• Optimal broadcast domination in polynomial time
• Relating broadcast independence and independence
• The Rectilinear Steiner Tree Problem is NP-Complete
• Unsolved algorithmic problems on trees

Cited in

(8)

• On the broadcast independence number of grid graph
• On the broadcast independence number of locally uniform 2-lobsters
• On the broadcast independence number of caterpillars
• Relating broadcast independence and independence
• Girth, minimum degree, independence, and broadcast independence
• On the broadcast independence number of circulant graphs
• Maximum boundary independent broadcasts in graphs and trees
• Boundary independent broadcasts in graphs

This page was built for publication: Algorithmic aspects of broadcast independence

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