The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex bisection width

DOI10.1016/S0166-218X(97)00112-1zbMath0902.68080MaRDI QIDQ1392537

Ralf Klasing

Publication date: 10 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

interconnection networksvertex-disjoint paths

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

A variable neighborhood search approach for the vertex bisection problem ⋮ A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem ⋮ Random walks, bisections and gossiping in circulant graphs ⋮ Two new integer linear programming formulations for the vertex bisection problem

Cites Work

• Unnamed Item
• New gossips and telephones
• Optimal algorithms for dissemination of information in generalized communication modes
• Optimal algorithms for broadcast and gossip in the edge-disjoint modes
• Gossiping in vertex-disjoint paths mode in \(d\)-dimensional grids and planar graphs
• Minimum-time line broadcast networks

This page was built for publication: The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex bisection width