Broadcast graph is NP-complete

DOI10.1007/978-3-031-83438-7_29MaRDI QIDQ6969480zbMATH OpenFDO

Authors Jinghan Xu, Zhiyuan Li

Publication date 20 June 2025

Full work available at URL https://doi.org/10.1007/978-3-031-83438-7_29

zbMATH Keywords

broadcast centerbroadcast graphscomputational complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Algorithms in computer science (68Wxx)

Cites work

• A minimum broadcast graph on 26 vertices
• A minimum broadcast graph on 63 vertices
• A new construction of broadcast graphs
• A simple construction of broadcast graphs
• A survey of gossiping and broadcasting in communication networks
• An Efficient Vertex Addition Method for Broadcast Networks
• Broadcast graphs using new dimensional broadcast schemes for Knödel graphs
• Compound constructions of broadcast networks
• Efficient construction of broadcast graphs
• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• Information Dissemination in Trees
• Minimal broadcast networks
• Minimum broadcast graphs
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• More broadcast graphs
• New gossips and telephones
• On the unique satisfiability problem
• Parameterized complexity of broadcasting in graphs
• Some minimum broadcast graphs
• Sparse broadcast graphs
• Subtree Isomorphism in O(n5/2)
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• The complexity of facets (and some facets of complexity)
• The complexity of finding a broadcast center
• The complexity of restricted spanning tree problems
• The minimum broadcast time problem for several processor networks
• Tight Bounds on Mimimum Broadcast Networks

Cited in

(1)

• Broadcasting under structural restrictions

This page was built for publication: Broadcast graph is NP-complete

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