A simple proof of the planar rectilinear Steiner ratio
| Autor: | Jeffrey S. Salowe |
|---|---|
| Rok vydání: | 1992 |
| Předmět: |
Discrete mathematics
Plane (geometry) Applied Mathematics Computer Science::Computational Geometry Management Science and Operations Research Minimum spanning tree Steiner tree problem Industrial and Manufacturing Engineering Combinatorics symbols.namesake Tree traversal Tree (descriptive set theory) Planar Simple (abstract algebra) TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Hardware_INTEGRATEDCIRCUITS symbols Point (geometry) Software MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Operations Research Letters. 12:271-274 |
| ISSN: | 0167-6377 |
| DOI: | 10.1016/0167-6377(92)90053-6 |
| Popis: | The rectilinear Steiner ratio is the worst-case ratio of the length of a rectilinear minimum spanning tree to the length of a minimal tree. Hwang proved that the ratio for point sets in the plane is 3/2. We provide a simple proof of the 3/2-bound. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|