检索结果-内蒙古大学图书馆

Generalised k-Steiner Tree Problems in Normed Planes

algorithmICA 2015年第1期71卷 66-86页

作者： Brazil, Marcus Ras, Charl J. Swanepoel, Konrad J. Thomas, Doreen A. Univ Melbourne Dept Elect & Elect Engn ARC Special Res Ctr Ultra Broadband Informat Netw Parkville Vic 3010 Australia Univ London London Sch Econ & Polit Sci Dept Math London WC2A 2AE England Univ Melbourne Dept Mech Engn Parkville Vic 3010 Australia

The 1-Steiner tree problem, the problem of constructing a Steiner minimum tree containing at most one Steiner point, has been solved in the Euclidean plane by Georgakopoulos and Papadimitriou using plane subdivisions called oriented Dirichlet cell partitions. Their algorithm produces an optimal solution within O(n (2)) time. In this paper we generalise their approach in order to solve the k-Steiner tree problem, in which the Steiner minimum tree may contain up to k Steiner points for a given constant k. We also extend their approach further to encompass other normed planes, and to solve a much wider class of problems, including the k-bottleneck Steiner tree problem and other generalised k-Steiner tree problems. We show that, for any fixed k, such problems can be solved in O(n (2k) ) time.

关键词： k-Steiner tree Bottleneck Steiner problem Network optimisation polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

COMPUTING THE EXPECTED MAXIMUM NUMBER OF VERTEX-DISJOINT S-T PATHS IN A PROBABILISTIC BASICALLY SERIES-PARALLEL DIGRAPH

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1993年第12期E76A卷 2089-2094页

作者： CHENG, P MASUYAMA, S Toyohashi Univ of Technology Toyohashi Japan

In this paper, we propose a polynomial time algorithm for computing the expected maximum number of vertex-disjoint s-t paths in a probabilistic basically series-parallel directed graph and a probabilistic series-parallel undirected graph with distinguished source s and sink t(s not equal t), where each edge has a mutually independent failure probability and each vertex is assumed to be failure-free.

关键词： PROBABILISTIC GRAPH EXPECTED MAXIMUM NUMBER OF VERTEX-DISJOINT S-T PATHS SERIES-PARALLEL UNDIRECTED GRAPH BASICALLY SERIES-PARALLEL DIRECTED GRAPH polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

On efficient domination for some classes of H-free bipartite graphs

引用

DISCRETE APPLIED MATHEMATICS 2019年 270卷 58-67页

作者： Brandstaedt, Andreas Mosca, Raffaele Univ Rostock Inst Informat D-18051 Rostock Germany Univ G DAnnunzio Dipartimento Econ I-65121 Pescara Italy

A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in C, is known to be NP-complete even for very restricted H-free graph classes such as for 2P(3)-free chordal graphs while it is solvable in polynomial time for P-6-free graphs. Here we focus on bipartite graphs: We show that (weighted) ED can be solved in polynomial time for H-free bipartite graphs when H is P-7 or lP(4) for fixed l, and similarly for P-9-free bipartite graphs with vertex degree at most 3, and when H is S-2,S-2,S-4 . Moreover, we show that ED is NP-complete for bipartite graphs with diameter at most 6. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Weighted efficient domination H-free bipartite graphs NP-completeness polynomial time algorithm Clique-width

来源：评论

学校读者我要写书评

暂无评论

A note on equitable Hamiltonian cycles

引用

DISCRETE APPLIED MATHEMATICS 2021年 303卷 127-136页

作者： Ophelders, Tim Lambers, Roel Spieksma, Frits C. R. Vredeveld, Tjark Michigan State Univ Dept Computat Math Sci & Engn E Lansing MI 48824 USA Eindhoven Univ Technol Dept Math & Comp Sci Eindhoven Netherlands Maastricht Univ Dept Quantitat Econ Maastricht Netherlands

Given a complete graph with an even number of vertices, and with each edge colored with one of two colors (say red or blue), an equitable Hamiltonian cycle is a Hamiltonian cycle that can be decomposed into two perfect matchings such that both perfect matchings have the same number of red edges. We show that, for any coloring of the edges, in any complete graph on at least 6 vertices, an equitable Hamiltonian cycle exists. (C) 2020 The Authors. Published by Elsevier B.V.

关键词： Equitable Hamiltonian cycle Colored complete graphs polynomial time algorithm Local search

来源：评论

学校读者我要写书评

暂无评论

Multiple sink location problem in path networks with a combinational objective

引用

OPTIMIZATION LETTERS 2021年第2期15卷 733-755页

作者： Luo, Taibo Li, Hongmei Ru, Shaofeng Tong, Weitian Xu, Yinfeng Xidian Univ Sch Econ & Management Xian 710126 Peoples R China Northwest Univ Sch Econ & Management Xian 710127 Peoples R China Eastern Michigan Univ Dept Comp Sci Ypsilanti MI 48165 USA Donghua Univ Glorious Sun Sch Business & Management Shanghai 200051 Peoples R China

In this paper, we consider the k-sink location problem in a path network with the goal of optimizing a combinational function of the maximum completion time and the total completion time. Let P= mml:mfenced close=")" open="("V,E be an undirected path network with n vertices. Each vertex has a positive weight, indicating the initial amount of supplies, and each edge has a positive length and a uniform capacity, which is the maximum amount of supplies that can enter the edge per unit time. Our goal is to identify k sink locations on the path P so that all supplies will be successfully evacuated and the given objective function is optimized. This paper presents two efficient polynomial time algorithms, which achieve O for k=(n(6)) for general k, respectively.

关键词： Sink location Path network Combinational objective polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Lot sizing problem with multi-mode replenishment and batch delivery

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2018年 81卷 123-133页

作者： Akbalik, Ayse Rapine, Christophe Univ Lorraine LCOMS Technopole Metz Metz France

We study the single-item uncapacitated lot sizing problem with multi-mode replenishment and batch deliveries (ULS-MMB). Specifically, we consider that each replenishment mode has a Full Truck Load (FTL) cost structure and incurs a fixed ordering cost plus a fixed cost per batch. This problem arises in practice when a retailer places the order with different suppliers in each period. We show that this problem is NP-hard even for a single period and under very restricted cost parameters. We then show that ULS-MMB can be transformed into a lot sizing problem with only one replenishment mode per period, that is, ULS-MMB is a special case of lot-sizing with time-varying batch sizes. This simple observation allows us to improve some results already known in the literature of multi-mode replenishment. We propose a very efficient 2-approximation algorithm and establish that the problem admits an FPTAS. Finally, we show that the problem restricted to two modes with divisible batch sizes can be solved in polynomial time. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Lot sizing Multi-mode Batch delivery Approximation algorithm polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Bicriteria scheduling of equal length jobs on uniform parallel machines

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第3期39卷 637-661页

作者： Zhao, Qiulan Yuan, Jinjiang Nanjing Univ Dept Math Nanjing 210093 Jiangsu Peoples R China Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

We study the bicriteria scheduling of equal length jobs on uniform parallel machines. By introducing a new scheduling model, called single-machine scheduling with generated completion times (shortly, GCT-scheduling), we show that the scheduling of equal length jobs on uniform parallel machines can be polynomially transformed into the single-machine GCT-scheduling with a special setting of generated completion times. In the GCT-scheduling, a sequence of completion times is given in advance and the job scheduled at the i-th position will be assigned the i-th completion time. We present a comprehensive study on the complexities of the bicriteria single-machine GCT-scheduling problems with respect to various regular criteria. We then turn these complexity results into the forms of bicriteria scheduling of equal length jobs on uniform (or identical) parallel machines. Our research generalizes the existing results on bicriteria scheduling of equal length jobs in the literature. Particularly, one of our results solves the open problem posed by Sarin and Prakash (J Comb Optim 8:227-240, 2004), which asks for minimizing the total weighted completion time subject to the optimality of minimizing the total number of tardy jobs on identical parallel machines, and we show that this problem is solvable in polynomial time.

关键词： Bicriteria scheduling Uniform parallel machines Generated completion times polynomial time algorithm NP-hardness

来源：评论

学校读者我要写书评

暂无评论

The k-in-a-Path Problem for Claw-free Graphs

引用

algorithmICA 2012年第1-2期62卷 499-519页

作者： Fiala, Jiri Kaminski, Marcin Lidicky, Bernard Paulusma, Daniel Univ Durham Sci Labs Dept Comp Sci Durham DH1 3LE England Charles Univ Prague Fac Math & Phys DIMATIA Prague 11800 Czech Republic Charles Univ Prague Inst Theoret Comp Sci IIT Prague 11800 Czech Republic Univ Libre Bruxelles Dept Comp Sci B-1050 Brussels Belgium

The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the k-Induced Disjoint Paths and the k-in-a-Cycle problem are solvable in polynomial time on claw-free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices (s (i) ,t (i) ) for i=1,aEuro broken vertical bar,k and is to test whether G contain k mutually induced paths P (i) such that P (i) connects s (i) and t (i) for i=1,aEuro broken vertical bar,k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs.

关键词： Induced path Claw-free graph polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Single machine hierarchical scheduling with customer orders and multiple job classes

引用

ANNALS OF OPERATIONS RESEARCH 1997年第s期70卷 127-143页

作者： Gupta, JND Ho, JC vanderVeen, JAA BALL STATE UNIV DEPT MANAGEMENTMUNCIEIN 47306 COLUMBUS STATE UNIV ABBOTT TURNER SCH BUSINESSCOLUMBUSGA 31907 NIJENRODE UNIV NETHERLANDS BUSINESS SCHNL-3621 BG BREUKELENNETHERLANDS

In this paper, we consider single machine bi-criteria scheduling problems where jobs are from multiple job classes and there are customer orders such that each customer order consists of at least one job from each of the job classes. A set-up time is needed whenever the machine is changed over from a job in one class to a job in another class. One objective is to minimize the makespan which is equivalent to minimizing the total set-up time. The other objective is to minimize total carrying costs of the customer orders. The carrying cost of a customer order is measured by the length of the time interval between the completion times of the first job and the last job in the customer order. We propose constructive polynomial time algorithms for the two hierarchical scheduling problems with these two objectives, i.e. the two scheduling problems in which one objective is to be optimized while holding the other objective fixed at its optimal value.

关键词： hierarchical scheduling bi-criteria multiple job-classes polynomial time algorithm Traveling Salesman Problem

来源：评论

学校读者我要写书评

暂无评论

An Efficient Pattern Matching algorithm for Ordered Term Tree Patterns

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2015年第6期E98A卷 1197-1211页

作者： Suzuki, Yusuke Shoudai, Takayoshi Uchida, Tomoyuki Miyahara, Tetsuhiro Hiroshima City Univ Grad Sch Informat Sci Hiroshima 7313194 Japan Kyushu Int Univ Fac Int Studies Kitakyushu Fukuoka 8058512 Japan

A term tree pattern is a rooted ordered tree pattern which consists of ordered tree structures with edge labels and structured variables with labels. All variables with the same label in a term tree pattern can be simultaneously replaced with ordered trees isomorphic to the same rooted ordered tree. Then, a term tree pattern is suitable for representing structural features common to tree structured data such as XML documents on the web, the secondary structures of RNA in biology and parse trees describing grammatical structures of natural languages. Let OTT be the set of all term tree patterns which have one or more variables with the same label. Let LOTT be the set of all term tree patterns t such that all variables in t have distinct labels. We remark that LOTT subset of OTT holds. In this paper, we consider a problem, called Matching problem for term tree patterns, of deciding whether or not a given rooted ordered tree T is obtained from a given term tree pattern t by replacing variables in t with rooted ordered trees. We show that Matching problem for term tree patterns in OTT is NP-complete, by giving a reduction from the string pattern matching problem, which is NP-complete. Next, by giving operations on an interval, which is a set containing all integers between two given integers representing vertex identifiers, we propose an efficient algorithm for solving Matching problem for term tree patterns in LOTT. Then, we show that, when an ordered tree having N vertices and a term tree pattern t. LOTT having n vertices are given, the proposed matching algorithm correctly solves this problem in O(nN) time.

关键词： ordered tree structured pattern graph pattern matching algorithm polynomial time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：