The complexity of broadcasting in planar and decomposable graphs

DOI10.1007/3-540-59071-4_50zbMath1528.68301MaRDI QIDQ6184371

Christian Schindelhauer, Andreas Jakoby, K. Ruediger Reischuk

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexitygraph algorithmsgraph decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• The complexity of broadcasting in planar and decomposable graphs
• Easy problems for tree-decomposable graphs
• Planar 3DM is NP-complete
• Graph minors. II. Algorithmic aspects of tree-width
• A survey of gossiping and broadcasting in communication networks
• Broadcast Networks of Bounded Degree
• Information Dissemination in Trees
• Broadcasting in Bounded Degree Graphs

This page was built for publication: The complexity of broadcasting in planar and decomposable graphs