Á¤º¸°úÇÐȸ ³í¹®Áö A : ½Ã½ºÅÛ ¹× ÀÌ·Ð
Current Result Document : 2 / 2
ÇѱÛÁ¦¸ñ(Korean Title) |
°³ÀÎ Åë½Å¸Á ¼³°è¸¦ À§ÇÑ ÃÖ¼Ò ºñ¿ë °æ·Î |
¿µ¹®Á¦¸ñ(English Title) |
Minimum Cost Path for Private Network Design |
ÀúÀÚ(Author) |
ÃÖÈ«½Ä
ÀÌÁÖ¿µ
Hongsik Choi
Ju-Young Lee
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 26 NO. 11 PP. 1373 ~ 1381 (1999. 11) |
Çѱ۳»¿ë (Korean Abstract) |
ÀÌ ³í¹®¿¡¼´Â Åë½Å¸Á ¼³°è ÀÀ¿ëºÐ¾ßÀÇ ¹®Á¦¸¦ ±×·¡ÇÁ ÀÌ·Ð ¹®Á¦·Î½á °í·ÁÇØ º¸¾Ò´Ù. °³º° ±â¾÷ü°¡ ¼·Î ¶³¾îÁø µÎ °÷À» ¿¬°áÇÏ°íÀÚ ÇÒ ¶§ °ø¿ëÅë½Å¸ÁÀÇ È¸¼±À» ºô·Á Åë½Å¸ÁÀ» ±¸ÃàÇÏ°Ô µÇ´Âµ¥ ¸¹Àº °æ¿ì ¿©·¯ Á¾·ùÀÇ È¸¼±µéÀÌ °ø±ÞµÊÀ¸·Î ¾î¶² ȸ¼±À» ¼±ÅÃÇÏ´À³ÄÀÇ ¹®Á¦°¡ »ý±ä´Ù. ÀϹÝÀûÀ¸·Î ºü¸¥ ȸ¼±(low delay)Àº ´À¸° ȸ¼±(high delay)¿¡ ºñÇØ ºñ½Î´Ù. ±×·¯³ª ¼ºñ½ºÀÇ Áú(Quality of Service)À̶ó´Â ¿ä±¸»çÇ×ÀÌ Á¾Á¾ Á¾´ÜÁö¿¬(end-to-end delay)½Ã°£¿¡ ÀÇÇØ °áÁ¤µÇ¹Ç·Î, ¹«Á¶°Ç ³·Àº °¡°ÝÀÇ È¸¼±¸¸À» »ç¿ëÇÒ ¼ö´Â ¾ø´Ù. °á±¹ °³º° ±â¾÷üÀÇ Åë½Å¸ÁÀ» À§ÇÑ Åë·Î¸¦ °ø¿ë Åë½Å¸Á À§¿¡ µ¤¾î¾º¿ö(overlaying) ±¸ÃàÇÏ´Â °ÍÀÇ ¿©ºÎ´Â µÎ °³ÀÇ »ó¹ÝµÈ ÀÎÀÚÀÇ °¡°Ý°ú ¼ÓµµÀÇ Á¶Àý¿¡ ´Þ·Á ÀÖ´Ù. µû¶ó¼ ÀϹÝÀûÀÎ ÃÖ¼Ò°æ·Î ã±âÀÇ º¯ÇüÀ̶ó ÇÒ ¼ö ÀÖ´Â ´ÙÀ½ÀÇ ¹®Á¦°¡ º» ³í¹®ÀÇ °ü½É»çÀÌ´Ù. µÎ °³ÀÇ ÁöÁ¡À» ¿¬°áÇϴµ¥ Á¾´ÜÁö¿¬½Ã°£ÀÇ ÇѰ踦 ¸¸Á·ÇÏ¸é¼ ÃÖ¼Ò°æºñ¸¦ °®´Â °æ·Î¿¡ ´ëÇÑ ÇØ°áÀ» À§ÇÏ¿©, ±×·¡ÇÁ ä»ö(coloring) ¹®Á¦¿Í ÃÖ´Ü°æ·Î ¹®Á¦¸¦ ÇÔ²² Æ÷ÇÔÇÏ´Â ±×·¡ÇÁ ÀÌ·ÐÀÇ ¹®Á¦·Î Á¤ÇüȽÃÄÑ »ìÆ캻´Ù. ¹è³¶¹®Á¦·ÎÀÇ º¯È¯À» ÅëÇØ ÀÌ ¹®Á¦´Â NP-completeÀÓÀ» Áõ¸íÇÏ¿´°í O(|E|D0) ½Ã°£¿¡ ÃÖÀû°ªÀ» ÁÖ´Â Àǻ缱Çü ¾Ë°í¸®Áò°ú O(|E|)½Ã°£ÀÇ ±Ù»ç ¾Ë°í¸®ÁòÀ» º¸¿´´Ù. Ưº°ÇÑ °æ¿ì¿¡ ´ëÇÑ O(|V|+|E|)½Ã°£°ú O(|E|©÷+|E||V| log|V|) ½Ã°£ ¾Ë°í¸®ÁòÀ» º¸¿´À¸¸ç ¹è³¶ ¹®Á¦ÀÇ ÇØ°áÃ¥°ú À¯»çÇÑ ±×¸®µð ÈÞ¸®½ºÆ½(greedy heuristic) ¾Ë°í¸®ÁòÀÌ ±×¹° ±¸Á¶(mesh) ±×·¡ÇÁ »ó¿¡¼ ÁÁÀº °á°ú¸¦ º¸¿©ÁÖ°í ÀÖÀ½À» ½ÇÇèÀ» ÅëÇØ È®ÀÎÇØ º¸¾Ò´Ù.
|
¿µ¹®³»¿ë (English Abstract) |
This paper considers a graph-theoretic problem motivated by a telecommunication network optimization. When a private organization wishes to connect two sites by leasing physical lines from a public telecommunications network, it is often the cases that several categories of lines are available, at different costs. Typically a faster (low delay) lines costs more than a slower (high delay) line. However, low cost lines cannot be used exclusively because the Quality of Service (QoS) requirements often impose a bound on the end-to-end delay. Therefore, overlaying a path on the public network involves two diametrically opposing factors: cost and delay. The following variation of the standard shortest path problem is thus of interest: the shortest route between the two sites that meets a given bound on the end-to-end delay. For this problem we formulate a graph-theoretical problem that has both a shortest path component as well as coloring component. Interestingly, the problem could be formulated as a knapsack problem. We have shown that the general problem is NP-complete. The optimal polynomial-time algorithms for some special cases and one heuristic algorithm for the general problem are described.
|
Å°¿öµå(Keyword) |
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|