Back to Search
Start Over
Lower bounds for rectilinear Steiner trees in bounded space
- Source :
- Information Processing Letters. 37:71-74
- Publication Year :
- 1991
- Publisher :
- Elsevier BV, 1991.
-
Abstract
- We prove that, in all dimensions, the total weight of a worst-case minimal rectilinear Steiner tree in the unit d-cube is at least n(d−1) d .
- Subjects :
- Discrete mathematics
Rectilinear Steiner tree
Computer Science::Computational Geometry
Space (mathematics)
Computational geometry
Upper and lower bounds
Steiner tree problem
Computer Science Applications
Theoretical Computer Science
Combinatorics
symbols.namesake
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
Bounded function
Signal Processing
Hardware_INTEGRATEDCIRCUITS
symbols
Computer Science::Data Structures and Algorithms
Unit (ring theory)
MathematicsofComputing_DISCRETEMATHEMATICS
Information Systems
Mathematics
Subjects
Details
- ISSN :
- 00200190
- Volume :
- 37
- Database :
- OpenAIRE
- Journal :
- Information Processing Letters
- Accession number :
- edsair.doi...........b72abcd350b9486d6162b3a2c5b29716
- Full Text :
- https://doi.org/10.1016/0020-0190(91)90136-6