Scholarlink

<p>An extensive facility location problem in a network is concerned with the location of special types of subgraphs such as subtrees or paths and can be considered as a natural extension of the classical single facility location problem. In this paper, we consider the bi-objective combinatorial optimization problem of locating a path-shaped facility in a tree network, which minimizes the most common two criteria, namely the center criterion and the median criterion. To solve the problem, we use two forms of the <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_617_Article_IEq1.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="11" /> </InlineMediaObject> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation>-constraint method. This method converts the proposed bi-objective optimization problem to a series of single constraint optimization subproblems. In the considered problem, each subproblem is a cent-dian problem that can be solved in <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_617_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="73" /> </InlineMediaObject> <EquationSource Format="TEX">\(O(n\log n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Efficient Solutions of Bi-objective Central-Median Path Problem on Tree Network

  • 期刊论文

  • 发表日期：

    2025年8月14日

查看全文
  • Abdallah W. Aboutahoun,
  • Fatma El-Safty

摘要

An extensive facility location problem in a network is concerned with the location of special types of subgraphs such as subtrees or paths and can be considered as a natural extension of the classical single facility location problem. In this paper, we consider the bi-objective combinatorial optimization problem of locating a path-shaped facility in a tree network, which minimizes the most common two criteria, namely the center criterion and the median criterion. To solve the problem, we use two forms of the \(\varepsilon \) ε -constraint method. This method converts the proposed bi-objective optimization problem to a series of single constraint optimization subproblems. In the considered problem, each subproblem is a cent-dian problem that can be solved in \(O(n\log n)\) O ( n log n ) time.