Graph Minors and Reliable Single Message Transmission

DOI10.1137/S0895480103421129MaRDI QIDQ5470796zbMATH OpenOpenAlexFDO

Authors André Kündgen, Michael J. Pelsmajer, Radhika Ramamurthi, Faith E. Fich

Publication date 1 June 2006

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480103421129

zbMATH Keywords

end-to-end communicationgraph minorsreliable transmissiontree decompositiontree-width

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) 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)

Recommendations

• k-robust single-message transmission
• Lower bounds for oblivious single-packet end-to-end communication
• Header-size lower bounds for end-to-end communication in memoryless networks
• scientific article; zbMATH DE number 1696686
• Message complexity versus space complexity in fault tolerant broadcast protocols

Cited in

(10)

• Expected reliability of communication protocols
• Header-size lower bounds for end-to-end communication in memoryless networks
• scientific article; zbMATH DE number 1696686 (Why is no real title available?)
• k-robust single-message transmission
• Slide—The Key to Polynomial End-to-End Communication
• Equitable list coloring and treewidth
• Log-Space Polynomial End-to-End Communication
• Finding Minors in Graphs with a Given Path Structure
• Lower bounds for oblivious single-packet end-to-end communication
• Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs

This page was built for publication: Graph Minors and Reliable Single Message Transmission

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