View Item 

Show simple item record

Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem

dc.contributor.authorKönemann, Jochenen_US
dc.contributor.authorSinha, Amitabhen_US
dc.contributor.authorLevin, Asafen_US
dc.date.accessioned2006-09-08T19:09:36Z
dc.date.available2006-09-08T19:09:36Z
dc.date.issued2004-11en_US
dc.identifier.citationKö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.issn1432-0541en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttps://hdl.handle.net/2027.42/41348
dc.description.abstractWe 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.extent966246 bytes
dc.format.extent3115 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypetext/plain
dc.language.isoen_US
dc.publisherSpringer-Verlag; Springer Science + Business Media Inc.en_US
dc.subject.otherComputer Scienceen_US
dc.subject.otherBicriteria Approximationen_US
dc.subject.otherComputer Science, Generalen_US
dc.subject.otherDegree-bounded Spanning Treesen_US
dc.subject.otherSpanning Treesen_US
dc.subject.otherApproximation Algorithmsen_US
dc.subject.otherSoftware Engineering/Programming and Operating Systemsen_US
dc.subject.otherComputer Hardwareen_US
dc.subject.otherComputer Systems Organization and Communication Networksen_US
dc.subject.otherData Structures, Cryptology and Information Theoryen_US
dc.subject.otherTheory of Computationen_US
dc.titleApproximating the Degree-Bounded Minimum Diameter Spanning Tree Problemen_US
dc.typeArticleen_US
dc.subject.hlbsecondlevelPhilosophyen_US
dc.subject.hlbsecondlevelMathematicsen_US
dc.subject.hlbtoplevelHumanitiesen_US
dc.subject.hlbtoplevelScienceen_US
dc.description.peerreviewedPeer Revieweden_US
dc.contributor.affiliationumBusiness School, University of Michigan, Ann Arbor, MI 48103, USAen_US
dc.contributor.affiliationotherDepartment of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, N2L 3G1, Canadaen_US
dc.contributor.affiliationotherFaculty of Industrial Engineering and Management, The Technion, Haifa 32000, Israelen_US
dc.contributor.affiliationumcampusAnn Arboren_US
dc.description.bitstreamurlhttp://deepblue.lib.umich.edu/bitstream/2027.42/41348/1/453_2004_Article_1121.pdfen_US
dc.identifier.doihttp://dx.doi.org/10.1007/s00453-004-1121-2en_US
dc.identifier.sourceAlgorithmicaen_US
dc.owningcollnameInterdisciplinary and Peer-Reviewed


Files in this item

Name:
453_2004_Article_1121.pdf
Size:
943.5KB
Format:
PDF
View/Open

Show simple item record

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.