%0 Journal Article
%T Research on the Approximate Algorithms for QoS Routing<br>QoS路由近似算法的研究
%A ZHANG Xin-Ming CHEN Guo-Liang Huang Liu-Sheng XU Yun
%A <br>张信明
%A 陈国良
%J 计算机科学
%D 2003
%I 
%X In general, finding a feasible route subject to multiple additive QoS constraints is an NP-complete problem. In this paper,we first analyze the constraints and their properties that can reflect the basic characteristics of a network and support the fundamental QoS requirements. Then,we show that the unicast QoS routing problem can be generalized as a Multiple Constrained Path(MCP) or Restricted Shortest Path(RSP) problem. Finally,We investigate the efficient approximate algorithms for MCP and RSP, and how to convert a RSP problem to an easier MCP problem.
%K QoS routing
%K Approximate algorithm
%K MCP
%K RSP
%K NPC<br>QoS
%K 路由近似算法
%K 服务质量
%K 网络资源
%K 计算机网络
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=0D007715DC122AE0&yid=D43C4A19B2EE3C0A&vid=340AC2BF8E7AB4FD&iid=CA4FD0336C81A37A&sid=03F1579EF92A5A32&eid=D767283A3B658885&journal_id=1002-137X&journal_name=计算机科学&referenced_num=2&reference_num=15