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

broadcasting; processor networks

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C90: Applications of graph theory

68M10: Network design and communication in computer systems

68R10: Graph theory (including graph drawing) in computer science

94C15: Applications of graph theory to circuits and networks

Related Items

A linear algorithm for finding the k‐broadcast center of a tree, The complexity of broadcasting in planar and decomposable graphs

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item