NATIONAL BIBLIOGRAPHY NUMBER
Number
۳۵۵۴پ
LANGUAGE OF THE ITEM
.Language of Text, Soundtrack etc
per
TITLE AND STATEMENT OF RESPONSIBILITY
Title Proper
بررسی پیچیدگی مسئله ای حداکثر جریان با قیدهای جداکننده دودویی
First Statement of Responsibility
/صنم جاهداورنگ
.PUBLICATION, DISTRIBUTION, ETC
Name of Publisher, Distributor, etc.
تبریز:دانشگاه تبریز ،دانشکده ریاضی
PHYSICAL DESCRIPTION
Specific Material Designation and Extent of Item
۱۰۴ص
NOTES PERTAINING TO PUBLICATION, DISTRIBUTION, ETC.
Text of Note
چاپی
CONTENTS NOTE
Text of Note
فاقد سی دی چکیده
DISSERTATION (THESIS) NOTE
Dissertation or thesis details and type of degree
کارشناسی ارشد
Discipline of degree
ریاضی‌کاربردی
Date of degree
۱۳۹۱/۰۵/۲۵
Body granting the degree
تبریز:دانشگاه تبریز ،دانشکده ریاضی
SUMMARY OR ABSTRACT
Text of Note
One of the most important combinatorial optimization problems in networktopic is that of determining the maximum flow possible from onegiven source node to a sink node under arc capacity and flow conservation constraints. We study the maximum flow problem in a networkwith some additional constraints that is called binary disjunctiv constraints. negative disjunctive constraint states that a certain pair of arcs in network cannot be simultaneously used for sending flow in a feasible solution. In contrast, positive disjunctive constraints force that forcertain pairs of arcs at least one arc has to carry flow in a feasible solution. It is convenient to represent the negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the arcs of the underlying network, and whose edges correspond to the binary disjunctiv constraints. Analogously, we represent the positive disjunctive constraints by a so-called forcing graph. For conflict graphs, we prove that the maximum flow problem is strongly NP-hard, even if every connected component of the conflict graph is isolated edge. In contrast to this, we show that for forcing graphs the problem can be solved efficiently if arbitrary flow values are allowed. If on the other hand the flow values are required to be integral we provide the sharp line between polynomially solvable and strongly NP-hard instances
TOPICAL NAME USED AS SUBJECT
Maximum flow problem
Max flow problem with lower bounds
Negative disjunctive constraints
Positive disjunctive constraints
Constraint graph
Conflict graph
PERSONAL NAME - PRIMARY RESPONSIBILITY
جاهداورنگ، صنم
PERSONAL NAME - SECONDARY RESPONSIBILITY
مهری تکمه،جواد، استاد راهنما
میرنیا، کمال، استادمشاور
ELECTRONIC LOCATION AND ACCESS
Public note
سیاه و سفید
نمایه‌سازی قبلی
