Study on the Problem of Constrained Minimum Spanning Tree(约束最小生成树问题研究)
本文对约束最小生成树问题提出一个算法，它的计算复杂性是O(n3).然后把约束最小生成树作为约束Steiner最小树的一个近似解，则近似解的性能比为.
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Zhejiang University Press
1999-01-01
|
| Series: | Zhejiang Daxue xuebao. Lixue ban |
| Subjects: | |
| Online Access: | https://doi.org/zjup/1008-9497.1999.26.2.28-32 |
| _version_ | 1797236612294246400 |
|---|---|
| author | CHENGuang-ting(陈光亭) ZHANGGuo-chuan(张国川) |
| author_facet | CHENGuang-ting(陈光亭) ZHANGGuo-chuan(张国川) |
| author_sort | CHENGuang-ting(陈光亭) |
| collection | DOAJ |
| description | 本文对约束最小生成树问题提出一个算法，它的计算复杂性是O(n3).然后把约束最小生成树作为约束Steiner最小树的一个近似解，则近似解的性能比为. |
| first_indexed | 2024-04-24T17:06:37Z |
| format | Article |
| id | doaj.art-cd3f7c51eefe4eb58a8615fba2d04f84 |
| institution | Directory Open Access Journal |
| issn | 1008-9497 |
| language | zho |
| last_indexed | 2024-04-24T17:06:37Z |
| publishDate | 1999-01-01 |
| publisher | Zhejiang University Press |
| record_format | Article |
| series | Zhejiang Daxue xuebao. Lixue ban |
| spelling | doaj.art-cd3f7c51eefe4eb58a8615fba2d04f842024-03-29T01:58:15ZzhoZhejiang University PressZhejiang Daxue xuebao. Lixue ban1008-94971999-01-012622832zjup/1008-9497.1999.26.2.28-32Study on the Problem of Constrained Minimum Spanning Tree(约束最小生成树问题研究)CHENGuang-ting(陈光亭)0ZHANGGuo-chuan(张国川)1Institute of Advanced Mathematics, Zhejiang University, Hangzhou 310027, China(浙江大学玉泉校区高等数学研究所，浙江 杭州 310027)Institute of Advanced Mathematics, Zhejiang University, Hangzhou 310027, China(浙江大学玉泉校区高等数学研究所，浙江 杭州 310027)本文对约束最小生成树问题提出一个算法，它的计算复杂性是O(n3).然后把约束最小生成树作为约束Steiner最小树的一个近似解，则近似解的性能比为.https://doi.org/zjup/1008-9497.1999.26.2.28-32生成树steiner树近似算法性能比 |
| spellingShingle | CHENGuang-ting(陈光亭) ZHANGGuo-chuan(张国川) Study on the Problem of Constrained Minimum Spanning Tree(约束最小生成树问题研究) Zhejiang Daxue xuebao. Lixue ban 生成树 steiner树 近似算法 性能比 |
| title | Study on the Problem of Constrained Minimum Spanning Tree(约束最小生成树问题研究) |
| title_full | Study on the Problem of Constrained Minimum Spanning Tree(约束最小生成树问题研究) |
| title_fullStr | Study on the Problem of Constrained Minimum Spanning Tree(约束最小生成树问题研究) |
| title_full_unstemmed | Study on the Problem of Constrained Minimum Spanning Tree(约束最小生成树问题研究) |
| title_short | Study on the Problem of Constrained Minimum Spanning Tree(约束最小生成树问题研究) |
| title_sort | study on the problem of constrained minimum spanning tree 约束最小生成树问题研究 |
| topic | 生成树 steiner树 近似算法 性能比 |
| url | https://doi.org/zjup/1008-9497.1999.26.2.28-32 |
| work_keys_str_mv | AT chenguangtingchénguāngtíng studyontheproblemofconstrainedminimumspanningtreeyuēshùzuìxiǎoshēngchéngshùwèntíyánjiū AT zhangguochuanzhāngguóchuān studyontheproblemofconstrainedminimumspanningtreeyuēshùzuìxiǎoshēngchéngshùwèntíyánjiū |