Approximation algorithms in graphs with known broadcast time of the base graph

DOI10.1007/978-3-030-95018-7_24MaRDI QIDQ6102286zbMATH OpenOpenAlexFDO

Authors Puspal Bhabak, Hovhannes A. Harutyunyan

Publication date 8 May 2023

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

Full work available at URL https://doi.org/10.1007/978-3-030-95018-7_24

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Approximation Algorithms for Minimum-Time Broadcast
• scientific article; zbMATH DE number 1875435
• scientific article; zbMATH DE number 219254
• Approximation algorithms for graph approximation problems
• Approximation algorithms for approximating graphs with bounded number of connected components
• On constant time approximation of parameters of bounded degree graphs
• A Broadcasting Algorithm with Time and Message Optimum on Arrangement Graphs
• Sublinear-time algorithms for approximating graph parameters
• Constant approximation for broadcasting in k-cycle graph
• Graph-Theoretic Concepts in Computer Science

Cites work

• A survey of gossiping and broadcasting in communication networks
• Approximation Algorithms for Minimum-Time Broadcast
• Broadcast problem in hypercube of trees
• Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem
• Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
• scientific article; zbMATH DE number 1670545 (Why is no real title available?)
• scientific article; zbMATH DE number 2079323 (Why is no real title available?)
• scientific article; zbMATH DE number 1775430 (Why is no real title available?)
• scientific article; zbMATH DE number 857072 (Why is no real title available?)
• Information Dissemination in Trees
• Linear Algorithm for Broadcasting in Unicyclic Graphs
• Methods and problems of communication in usual networks
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• On broadcasting in unicyclic graphs
• The minimum broadcast time problem for several processor networks

Cited in

(3)

• A tight upper bound on acquaintance time of graphs
• Parameterized Complexity of Broadcasting in Graphs
• A note to non-adaptive broadcasting

This page was built for publication: Approximation algorithms in graphs with known broadcast time of the base graph

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