The complexity of broadcasting in planar and decomposable graphs

DOI10.1016/S0166-218X(97)00110-8zbMath0901.68086MaRDI QIDQ1392535

Christian Schindelhauer, Andreas Jakoby, K. Ruediger Reischuk

Publication date: 2 December 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

broadcastingprocessor networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Related Items (5)

The complexity of broadcasting in planar and decomposable graphs ⋮ Data transmission in processor networks ⋮ The complexity of broadcasting in planar and decomposable graphs ⋮ A linear algorithm for finding the k‐broadcast center of a tree ⋮ Broadcasting in weighted trees under the postal model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• The decomposition of graphs into \(k\)-connected components
• 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