The directed minimum-degree spanning tree problem

DOI10.1007/3-540-45294-X_20MaRDI QIDQ4474221zbMATH OpenFDO

Authors Radha Krishnan, Balaji Raghavachari

Publication date 4 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2245/22450232.htm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 742978
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
• Approximating the degree-bounded minimum diameter spanning tree problem
• Approximating the degree-bounded minimum diameter spanning tree problem

Cited in

(9)

• Finding minimum cost directed trees with demands and capacities
• Complexity of the directed spanning cactus problem
• Near-linear time algorithm for approximate minimum degree spanning trees
• What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
• scientific article; zbMATH DE number 4173002 (Why is no real title available?)
• On the directed degree-preserving spanning tree problem
• On the directed full degree spanning tree problem
• scientific article; zbMATH DE number 742978 (Why is no real title available?)
• A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

Describes a project that uses

Uses Software

• GraphBase

This page was built for publication: The directed minimum-degree spanning tree problem

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