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

Complexity of correspondence H-colourings

DISCRETE APPLIED MATHEMATICS 2020年 281卷 235-245页

作者： Feder, Tomas Hell, Pavol 268 Waverley St Palo Alto CA 94301 USA Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

Correspondence homomorphisms generalize standard homomorphisms as well as correspondence colourings (also known as DP-colourings). For a fixed target graph H, we study the problem of deciding whether an input graph G, with each edge labelled by a pair of permutations of V(H), admits a homomorphism to H 'corresponding' to the labels. Homomorphisms to H are called H-colourings, and we employ the similar term correspondence H-colourings for correspondence homomorphisms to H. We classify the complexity of this problem as a function of the fixed graph H. It turns out that there is dichotomy - each of the problems is polynomial-time solvable or NP-complete. While most graphs H yield NP-complete problems, there are interesting cases of graphs H for which the problem can be solved in polynomial time by Gaussian elimination. We also classify the complexity of the analogous correspondence list homomorphism problems, and also the complexity of a bipartite version of both problems. We give detailed proofs for the case when H is reflexive, and, for the record, sketch the remaining proofs. (c) 2019 Elsevier B.V. All rights reserved.

关键词： Graph homomorphisms H-colourings Correspondence colourings DP-colourings Dichotomy NP-completeness polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling no-wait robotic cells with two and three machines

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2000年第2期123卷 303-314页

作者： Agnetis, A Univ Siena Dipartimento Ingn Informaz I-53100 Siena Italy

A no-wait robotic cell is an automated m-machine flow shop in which one robot is used to move the parts from a machine to the next, as well as between the machines and the input/output devices. Parts are not allowed to wait, either on a machine or on the robot. The problem is to sequence the parts and, concurrently, schedule the robot moves in order to maximize productivity. In the two-machine case, we show that the problem is solvable in time O(n log n) by reducing it to the classical two-machines no-wait flow shop. For the three-machine case and identical parts, it is shown that it is sufficient to consider robot move cycles in which all the machines are visited once or twice. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： robotic cells no-wait flow shop polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespan

引用

OPTIMIZATION LETTERS 2017年第1期11卷 165-177页

作者： Lazarev, Alexander A. Arkhipov, Dmitry I. Werner, Frank Russian Acad Sci VA Trapeznikov Inst Control Sci Moscow Russia Lomonosov Moscow State Univ Moscow Russia Moscow Inst Phys & Technol Dolgoprudnyi Russia Natl Res Univ Higher Sch Econ Int Lab Decis Choice & Anal Moscow Russia Otto von Guericke Univ Inst Math Optimizat Fac Math Magdeburg Germany

The following special case of the classical NP-hard scheduling problem 1 vertical bar r(j)vertical bar Lmax is considered. There is a set of jobs N = {1, 2,..., n} with identical processing times p(j) = p for all jobs j epsilon N. All jobs have to be processed on a single machine. The optimization criterion is the minimization of maximum lateness Lmax. We analyze algorithms for the makespan problem 1 vertical bar r(j)vertical bar C-max, presented by Garey et al. (SIAM J Comput 10(2): 256-269, 1981), Simons (A fast algorithm for single processor scheduling. In: 19th Annual symposium on foundations of computer science (Ann Arbor, Mich., 1978, 1978) and Benson's algorithm (J Glob Optim 13(1): 1-24, 1998) and give two polynomial algorithms to solve the problem under consideration and to construct the Pareto set with respect to the criteria Lmax and Cmax. The complexity of the presented algorithms is O(Q.n log n) and O(n(3) log n), respectively, where 10(-Q) is the accuracy of the input-output parameters.

关键词： Scheduling Single machine Equal processing times polynomial algorithms Bi-criteria problem

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for Some Competitive Location Centroid Problems on Paths, Trees and Graphs

引用

ALGORITHMICA 2013年第3期66卷 615-640页

作者： Lazar, Avivit Tamir, Arie Tel Aviv Univ Sch Math Sci IL-69978 Tel Aviv Israel

We consider a common scenario in competitive location, where two competitors (providers) place their facilities (servers) on a network, and the users, which are modeled by the nodes of the network, can choose between the providers. We assume that each user has an inelastic demand, specified by a positive real weight. A user is fully served by a closest facility. The benefit (gain) of a competitor is his market share, i.e., the total weight (demand) of the users served at his facilities. In our scenario the two providers, called the leader and the follower, sequentially place p and r servers, respectively. After the leader selects the locations for his p servers, the follower will determine the optimal locations for his r servers, that maximize his benefit. An (r,p)-centroid is a set of locations for the p servers of the leader, that will minimize the maximum gain of the follower who can establish r servers. In this paper we focus mainly on the cases where either the leader or the follower can establish only one facility, i.e., either p=1, or r=1. We consider two versions of the model. In the discrete case the facilities can be established only at the nodes, while in the absolute case they can be established anywhere on the network. For the (r,1)-centroid problem, we show that it is strongly NP-hard for a general graph, but can be approximated within a factor e/(e-1). On the other hand, when the graph is a tree, we provide strongly polynomial algorithms for the (r,p)-centroid model, whenever p is fixed. For the (1,1)-centroid problem on a general graph, we improve upon known results, and give the first strongly polynomial algorithm. The discrete (1,p)-centroid problem has been known to be NP-hard even for a subclass of series-parallel graphs with pathwidth bounded by 6. In view of this result, we consider the discrete and absolute (1,p) centroid models on a tree, and present the first strongly polynomial algorithms. Further improvements are shown when the tree is a p

关键词： Competitive location problems Centroids Paths Trees polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms FOR INTERVAL CATCH DIGRAPHS

引用

DISCRETE APPLIED MATHEMATICS 1994年第1-2期51卷 147-157页

作者： PRISNER, E Mathematisches Seminar Universit&auml t Hamburg Bundesstr. 55 2000 Hamburg 13 Germany

A family ((S(v), T(v))\v is-an-element-of V) of ordered pairs of intervals of the real line, each S, containing its corresponding T(v), is called a nest representation. A directed graph D = (V, A) is an interval nest digraph if there is some nest representation with index set V such that xy is-an-element-of A if and only if S(x) and T(y) not-equal theta. Interval catch digraphs allow nest representations where each set T(v) contains just one element. In this paper we show that the following problems can be solved efficiently for interval catch digraphs: (1) The RECOGNITION problem, (2) CLIQUE, CHROMATIC NUMBER, INDEPENDENT SET, PARTITION INTO CLIQUES and (3) KERNEL-finding an independent and absorbing vertex set, and SOLUTION-finding an independent and dominating vertex set. The problems of (2) and (3) can be solved even for interval nest digraphs if a nest representation is known.

关键词： INTERVAL DIGRAPHS polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Graph models for scheduling systems with machine saturation property

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2006年第2期63卷 329-340页

作者： Dell'Olmo, P Gentili, M Univ Salerno Dipartimento Matemat & Informat I-84084 Fisciano Salerno Italy Univ Roma La Sapienza Dipartimento Stat Probabilita & Stat Applicate I-00185 Rome Italy

Let T = {T-1, T-2, . . . , T-n} be a set of n independent tasks and P = {P-1, P-2, . . . , P-m} a set of m processors. During each time instant, each processor can be used by a single task at most. A schedule is for each task an allocation of one or more time intervals to one or more processors. A schedule is said to be optimal if it minimizes the maximum completion time. We say a schedule S has the machine saturation property (MS property) if, at any time instant of task execution, all the machines are simultaneously busy. In this paper, we analyze the conditions under which a parallel scheduling system allows a schedule with the MS property. While for some simple models the analytical conditions can be easily stated, a graph model approach is required when conflicts of processor usage are present. For this reason, we define the class of saturated graphs that correspond to scheduling systems with the MS property. We present efficient graph recognition algorithms to verify the MS property directly on some classes of saturated graphs.

关键词： makespan multiprocessor task scheduling polynomial algorithms intersection graphs

来源：评论

学校读者我要写书评

暂无评论

The balanced connected subgraph problem

引用

DISCRETE APPLIED MATHEMATICS 2022年 319卷 111-120页

作者： Bhore, Sujoy Chakraborty, Sourav Jana, Satyabrata Mitchell, Joseph S. B. Pandit, Supantha Roy, Sasanka TU Wien Algorithms & Complex Grp Vienna Austria Indian Stat Inst Kolkata India SUNY Stony Brook Stony Brook NY USA Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujarat India

The problem of computing induced subgraphs that satisfy some specified restrictions arises in various applications of graph algorithms and has been well studied. In this paper, we consider the following Balanced Connected Subgraph (BCS) problem. The input is a graph G = (V, E), with each vertex in the set V having an assigned color, "red"or "blue". We seek a maximum-cardinality subset V ' subset of V of vertices that is color-balanced (having exactly |V '|/2 red vertices and |V '|/2 blue vertices), such that the subgraph induced by the vertex set V ' in G is connected. We show that the BCS problem is NP-hard, even for bipartite graphs G (with red/blue color assignment not necessarily being a proper 2-coloring). Further, we consider this problem on various graph classes, e.g., planar graphs, chordal graphs, trees, split graphs, bipartite graphs with a proper red/blue 2-coloring, and graphs with diameter 2. For each of these classes we either prove NP-hardness or design a polynomial time algorithm.(c) 2021 Elsevier B.V. All rights reserved.

关键词： Balanced connected subgraph Trees Split graphs Chordal graphs Planar graphs Bipartite graphs polynomial algorithms NP-hard

来源：评论

学校读者我要写书评

暂无评论

Infeasible Interior-Point Methods for Linear Optimization Based on Large Neighborhood

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2016年第2期170卷 562-590页

作者： Asadi, Alireza Roos, Cornelis Delft Univ Technol Fac Elect Engn Comp Sci & Math POB 5031 NL-2600 GA Delft Netherlands

In this paper, we design a class of infeasible interior-point methods for linear optimization based on large neighborhood. The algorithm is inspired by a full-Newton step infeasible algorithm with a linear convergence rate in problem dimension that was recently proposed by the second author. Unfortunately, despite its good numerical behavior, the theoretical convergence rate of our algorithm is worse up to square root of problem dimension.

关键词： Linear optimization Primal-dual infeasible interior-point methods polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

THE COMPLEXITY OF LIFTED INEQUALITIES FOR THE KNAPSACK-PROBLEM

引用

DISCRETE APPLIED MATHEMATICS 1992年第2期39卷 113-123页

作者： HARTVIGSEN, D ZEMEL, E NORTHWESTERN UNIV JL KELLOGG GRAD SCH MANAGEMENTDEPT MANAGERIAL ECON & DECIS SCIEVANSTONIL 60208 USA

It is well known that one can obtain facets and valid inequalities for the knapsack polytope by lifting simple inequalities associated with minimal covers. We study the complexity of lifting. We show that recognizing integral lifted facets or valid inequalities can be done in O(n2) time, even if the minimal cover from which they are lifted is not given. We show that the complexities of recognizing nonintegral lifted facets and valid inequalities are similar, respectively, to those of recognizing general (not necessarily lifted) facets and valid inequalities. Finally, we show that recognizing valid inequalities is in co-NPC while recognizing facets is in D(p). The question of whether recognizing facets is complete for D(p) is open.

关键词： KNAPSACK POLYTOPE FACETS VALID INEQUALITIES COMPUTATIONAL COMPLEXITY LIFTING polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

FLOW MANAGEMENT IN FLEXIBLE MANUFACTURING CELLS WITH PIPELINE OPERATIONS

引用

MANAGEMENT SCIENCE 1993年第3期39卷 294-306页

作者： AGNETIS, A LUCERTINI, M NICOLO, F UNIV ROMA TOR VERGATA DIPARTIMENTO INGN ELETTRONI-00133 ROMEITALY

The problem of flow management for a class of flexible manufacturing cells is considered. The cell is designed for cyclic production of one product. This product is characterized by a sequence of operations of given length and each requiring a set of resources;the problem is therefore to allocate such resources and scheduling the operations in order to maximize the throughput. A general model is proposed and several special cases are discussed, corresponding to either polynomial or NP-complete problems. The cases analyzed differ from each other in the number of operating machines and in the number of product units present at the same time in the cell. The solution to the polynomial problems is given in terms of shortest path on particular networks.

关键词： PRODUCTION SCHEDULING FLOW MANAGEMENT FLEXIBLE MANUFACTURING CELLS TASK SYNCHRONIZATION polynomial algorithms NP-COMPLETE PROBLEMS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：