Presentation | 2003/11/13 Study on fast steiner tree calculation algorithm Koji SUGISONO, Yasuo SHIGA, Seisho YASUKAWA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Heuristic algorithm for steiner tree is promissive for reduction of traffic volume, avoidance of congestion, and so on. The calculation speed of the algorithms are required to be fast for implementation of network node, such as router. But the steiner tree problem is NP complete, so it is hard to compute the complete soultion within polynominal time. KMB algorithm is fast and calculates multicast path whose cost is reduced effectively. The calculation result is composed of shortest path between egress points or ingress and egress point of route. So cost of the calculation result depends on how long shared link of two shortest path exists. We propose fast algorithm modifying KMB algorithm to solve the dependency of shortest path selection. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Multicast / Route Calculation / Steiner Tree |
Paper # | NS2003-156,CQ2003-73,TM2003-34 |
Date of Issue |
Conference Information | |
Committee | NS |
---|---|
Conference Date | 2003/11/13(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Network Systems(NS) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Study on fast steiner tree calculation algorithm |
Sub Title (in English) | |
Keyword(1) | Multicast |
Keyword(2) | Route Calculation |
Keyword(3) | Steiner Tree |
1st Author's Name | Koji SUGISONO |
1st Author's Affiliation | NTT Network Service Systems Laboratories() |
2nd Author's Name | Yasuo SHIGA |
2nd Author's Affiliation | NTT Network Service Systems Laboratories |
3rd Author's Name | Seisho YASUKAWA |
3rd Author's Affiliation | NTT Network Service Systems Laboratories |
Date | 2003/11/13 |
Paper # | NS2003-156,CQ2003-73,TM2003-34 |
Volume (vol) | vol.103 |
Number (no) | 442 |
Page | pp.pp.- |
#Pages | 4 |
Date of Issue |