|
|
Article: New findings from K. Chaudhuri and co-authors describe advances in computer science.
- Article from:
- Computer Weekly News
- Article date:
- November 12, 2009
CopyrightCOPYRIGHT 2009 NewsRX. This material is published under license from the publisher through the Gale Group, Farmington Hills, Michigan. All inquiries regarding rights should be directed to the Gale Group. (Hide copyright information)
|
"In the minimum-degree minimum spanning tree (MDMST) problem. we are given a graph G, and the goal is to find a minimum spanning tree (MST) T, such that the maximum degree of T is as small as possible. This problem is NP-hard and generalizes the Hamiltonian path problem," scientists writing in the journal Theoretical Computer Science report.
"We give an algorithm that outputs an MST of degree at most 2 Delta(OPT) (G) + 0(Delta(OPT) (G)), where Delta(OPT) (G) denotes the degree of the optimal tree. This result improves on a previous result of Fischer [T. Fischer, Optimizing the degree of minimum weight spanning trees. Technical Report 14853, Dept. of Computer ...