Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem
dc.contributor.author | Könemann, Jochen | en_US |
dc.contributor.author | Sinha, Amitabh | en_US |
dc.contributor.author | Levin, Asaf | en_US |
dc.date.accessioned | 2006-09-08T19:09:36Z | |
dc.date.available | 2006-09-08T19:09:36Z | |
dc.date.issued | 2004-11 | en_US |
dc.identifier.citation | Könemann, Jochen; Levin, Asaf; Sinha, Amitabh; (2004). "Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem." Algorithmica 41(2): 117-129. <http://hdl.handle.net/2027.42/41348> | en_US |
dc.identifier.issn | 1432-0541 | en_US |
dc.identifier.issn | 0178-4617 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/41348 | |
dc.description.abstract | We consider the problem of finding a minimum diameter spanning treewith maximum node degree $B$ in a complete undirected edge-weightedgraph. We provide an $O(sqrt{log_Bn})$-approximation algorithm for theproblem. Our algorithm is purely combinatorial, and relies on acombination of filtering and divide and conquer. | en_US |
dc.format.extent | 966246 bytes | |
dc.format.extent | 3115 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Springer-Verlag; Springer Science + Business Media Inc. | en_US |
dc.subject.other | Computer Science | en_US |
dc.subject.other | Bicriteria Approximation | en_US |
dc.subject.other | Computer Science, General | en_US |
dc.subject.other | Degree-bounded Spanning Trees | en_US |
dc.subject.other | Spanning Trees | en_US |
dc.subject.other | Approximation Algorithms | en_US |
dc.subject.other | Software Engineering/Programming and Operating Systems | en_US |
dc.subject.other | Computer Hardware | en_US |
dc.subject.other | Computer Systems Organization and Communication Networks | en_US |
dc.subject.other | Data Structures, Cryptology and Information Theory | en_US |
dc.subject.other | Theory of Computation | en_US |
dc.title | Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Philosophy | en_US |
dc.subject.hlbsecondlevel | Mathematics | en_US |
dc.subject.hlbtoplevel | Humanities | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Business School, University of Michigan, Ann Arbor, MI 48103, USA | en_US |
dc.contributor.affiliationother | Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, N2L 3G1, Canada | en_US |
dc.contributor.affiliationother | Faculty of Industrial Engineering and Management, The Technion, Haifa 32000, Israel | en_US |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/41348/1/453_2004_Article_1121.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1007/s00453-004-1121-2 | en_US |
dc.identifier.source | Algorithmica | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.