A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
type: Item
instance of: scholarly article
title: A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
zbMATH Open document ID: 1155.05059
author: Guohui Yao
author: Daming Zhu
author: Hengwu Li
author: Shaohan Ma
published in: Discrete Mathematics
publication date: 2008-07-11T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 94A99
zbMATH DE Number: 5300651
zbMATH Keywords: algorithm
zbMATH Keywords: spanning tree
zbMATH Keywords: directed acyclic graph
zbMATH Keywords: minimum time broadcast
MaRDI profile type: Publication
full work available at URL: j.disc.2007.07.105
OpenAlex ID: W2070543274
cites work: Q4542563
cites work: Fast Gossiping by Short Messages
cites work: Q4252389
cites work: Minimum-time line broadcast networks
cites work: Q4796194
cites work: Methods and problems of communication in usual networks
cites work: Q4763417
cites work: Approximating the Minimum-Degree Steiner Tree to within One of Optimal
cites work: Topological design of centralized computer networks—formulations and algorithms
cites work: A survey of gossiping and broadcasting in communication networks
cites work: Q4870160
cites work: Gossiping in vertex-disjoint paths mode in \(d\)-dimensional grids and planar graphs
cites work: Optimal algorithms for broadcast and gossip in the edge-disjoint modes
cites work: The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex bisection width
cites work: Approximation algorithms for finding low-degree subgraphs
cites work: A matter of degree
cites work: Approximation Algorithms for Minimum-Time Broadcast
cites work: Q4130999
cites work: Q4474221
cites work: Many birds with one stone
cites work: Approximation algorithms for combinatorial optimization. 3rd international workshop, APPROX 2000, Saarbrücken, Germany, September 5--8, 2000. Proceedings
DOI: 10.1016/J.DISC.2007.07.105
description: scientific article; zbMATH DE number 5300651