東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Multiroute flow problem.

Du, Donglei.

Linked to FindBook

Google Book

Amazon

博客來

Multiroute flow problem.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Multiroute flow problem./
Author:	Du, Donglei.
Description:	62 p.
Notes:	Source: Dissertation Abstracts International, Volume: 64-07, Section: B, page: 3362.
Contained By:	Dissertation Abstracts International64-07B.
Subject:	Computer Science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3098536

Multiroute flow problem.
Du, Donglei.

Multiroute flow problem. - 62 p.

Source: Dissertation Abstracts International, Volume: 64-07, Section: B, page: 3362.

Thesis (Ph.D.)--The University of Texas at Dallas, 2003.

Flow problems and their variants have attracted considerable attention from both practical and theoretical points of view over the last forty years. On the practical side, they find applications in telecommunication, routing, VLSI, scheduling, transportation, networks design, and so forth. And on the theoretical side, they have deep connections with many other combinatorial objects, such as cuts, cycles, paths; as well as other mathematical disciplines, like polyhedral combinatorics, finite metrics, matriods, etc.Subjects--Topical Terms:

626642
Computer Science.

Multiroute flow problem.
LDR:03897nmm 2200313 4500 001 1856055
005 20040616162818.5
008 130614s2003 eng d
035 $a (UnM)AAI3098536
035 $a AAI3098536
040 $a UnM $c UnM
100 1 $a Du, Donglei. $3 1943849
245 1 0 $a Multiroute flow problem.
300 $a 62 p.
500 $a Source: Dissertation Abstracts International, Volume: 64-07, Section: B, page: 3362.
500 $a Supervisor: R. Chandrasekaran.
502 $a Thesis (Ph.D.)--The University of Texas at Dallas, 2003.
520 $a Flow problems and their variants have attracted considerable attention from both practical and theoretical points of view over the last forty years. On the practical side, they find applications in telecommunication, routing, VLSI, scheduling, transportation, networks design, and so forth. And on the theoretical side, they have deep connections with many other combinatorial objects, such as cuts, cycles, paths; as well as other mathematical disciplines, like polyhedral combinatorics, finite metrics, matriods, etc.
520 $a A standard flow problem involves shipping one or more commodities from one specified set of nodes (sources) to another set of nodes (destinations) in a single network, while preserving the capacity constraints on all arcs and the flow conservation constraints on all nodes except the sources and destinations. The most often used objective is to maximize the total flow shipped from the sources to the destinations. The resultant problem is called the maximum flow problem (MFP).
520 $a As a generalization, in this study we consider the <italic>multiroute fbw problem</italic>, in which each unit of flow is split evenly and sent along multiple edge/vertex-disjoint paths between each source and destination pairs. Such flows are robust against physical links/nodes failures in the network, and can tolerate up to a certain number of failed links/nodes.
520 $a There are two approaches to solve these problems. First, they can be solved as linear programs (LP) method in strongly polynomial time. However, this general-purpose method is very unsatisfactory here mainly because the order of the polynomial is high. The second theme is to apply a combinatorial method, like the augmenting-path approach, which amounts to exploiting the special structures underlying these problems. These special-purpose methods often lead to more efficient algorithms. Therefore we will focus on combinatorial methods, especially, the augmenting-path method, in this study.
520 $a In Chapter 1 we introduce the problem and review related work. Both Chapter 2 and 3 deal with the single commodity <italic>multiroute maximum flow problem </italic>. In Chapter 2, we devise an algorithm based on Newton's method, and in Chapter 3, we develop an algorithm based on the augmenting-path technique to solve this problem. In Chapter 4, we investigate the single commodity <italic> multiroute minimum-cost fbw problem</italic>, we propose two algorithms, one based on binary-search, and another based on successive <italic>m</italic>-path technique, to solve this problem. Both Chapter 5 and 6 treat the two-commodity multi-route maximum flow problem. In Chapter 5, we design an augmenting-path algorithm to solve the case with one of the two commodities being sent along double paths. In Chapter 6, we report some partial results on the case with both the commodities being sent along double paths, and explain why the previous techniques cannot be extended to this case. Finally, in Chapter 7, we discuss some future research problems.
590 $a School code: 0382.
650 4 $a Computer Science. $3 626642
650 4 $a Operations Research. $3 626629
690 $a 0984
690 $a 0796
710 2 0 $a The University of Texas at Dallas. $3 1018411
773 0 $t Dissertation Abstracts International $g 64-07B.
790 1 0 $a Chandrasekaran, R., $e advisor
790 $a 0382
791 $a Ph.D.
792 $a 2003
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3098536