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

Scheduling jobs with mixed processing times, arbitrary precedence constraints and maximum cost criterion

COMPUTERS & INDUSTRIAL ENGINEERING 2013年第1期64卷 273-279页

作者： Debczynski, Marek Gawiejnowicz, Stanislaw Adam Mickiewicz Univ Fac Math & Comp Sci PL-61614 Poznan Poland

We consider single-machine scheduling problems with variable job processing times, arbitrary precedence constraints and maximum cost criterion. We show how to solve the problems in polynomial time in the cases when job processing times are described by functions of the same type or when they are mixed, i.e. some of them are fixed, while the other ones are variable and take into account the effects of learning, ageing or job deterioration.

关键词： Scheduling Precedence constraints Maximum cost Job deterioration Learning/aeging effect polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Maximum weight independent sets in (P₆, co-banner)-free graphs

引用

INFORMATION PROCESSING LETTERS 2013年第3期113卷 89-93页

作者： Mosca, Raffaele Univ G DAnnunzio Dipartimento Econ I-65127 Pescara Italy

The Maximum Weight Independent Set (mWIS) Problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated problem on graphs, it is well known to be NP-complete and hard to approximate. Several graph classes for which MWIS can be solved in polynomial time have been introduced in the literature. This note shows that MWIS can be solved in polynomial time for (P-6, co-banner)-free graphs - where a P-6 is an induced path of 6 vertices and a co-banner is a graph with vertices a, b, c, d, e and edges al), bc, cd, ce, de - so extending different analogous known results for other graph classes, namely, P-4-free, 2K(2)-free, (P-5, co-banner)-free, and (P-6, triangle)-free graphs. The solution algorithm is based on an idea/algorithm of Farber (1989) [10], leading to a dynamic programming approach for MWIS, and needs none of the aforementioned known results as sub-procedure. (C) 2012 Published by Elsevier B.V.

关键词： Graph algorithms Maximum Weight Independent Set Problem polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

The complexity of the proper orientation number

引用

INFORMATION PROCESSING LETTERS 2013年第19-21期113卷 799-803页

作者： Ahadi, A. Dehghan, A. Sharif Univ Technol Dept Math Sci Tehran Iran Amirkabir Univ Technol Dept Math & Comp Sci Tehran Iran

A proper orientation of a graph G = (V, E) is an orientation D of E(G) such that for every two adjacent vertices v and u, d((D) over bar)(v) not equal d((D) over bar)(u) where d((D) over bar)(v) is the number of edges with head v in D. The proper orientation number of G is defined as (chi) over right arrow (G) = min(D is an element of Gamma) max(v is an element of v)(G)d((D) over bar)(v) where Gamma is the set of proper orientations of G. We have chi(G) 1 <= (chi) over right arrow (G) <= Delta(G), where chi(G) and Delta(G) denote the chromatic number and the maximum degree of G, respectively. We show that, it is NP-complete to decide whether (chi) over right arrow (G) = 2, for a given planar graph G. Also, we prove that there is a polynomial time algorithm for determining the proper orientation number of 3-regular graphs. In sharp contrast, we will prove that this problem is NP-hard for 4-regular graphs. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Computational complexity Proper orientation Vertex coloring NP-completeness Planar 3-SAT (type 2) Graph orientation polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Complexity of trails, paths and circuits in arc-colored digraphs

引用

DISCRETE APPLIED MATHEMATICS 2013年第6期161卷 819-828页

作者： Gourves, Laurent Lyra, Adria Martinhon, Carlos A. Monnot, Jerome Univ Paris 09 LAMSADE F-75775 Paris France Univ Fed Rural Rio de Janeiro Inst Multidisciplinar UFRRF Rio De Janeiro Brazil Univ Fed Fluminense Inst Computat Niteroi RJ Brazil

We deal with different algorithmic questions regarding properly arc-colored s-t trails, paths and circuits in arc-colored digraphs. Given an arc-colored digraph D-C with c >= 2 colors, we show that the problem of determining the maximum number of arc disjoint properly arc-colored s-t trails can be solved in polynomial time. Surprisingly, we prove that the determination of a properly arc-colored s-t path is NP-complete even for planar digraphs containing no properly arc-colored circuits and c = Omega (n), where n denotes the number of vertices in D-C. If the digraph is an arc-colored tournament, we show that deciding whether it contains a properly arc-colored circuit passing through a given vertex x (resp., properly arc-colored Hamiltonian s-t path) is NP-complete for c >= 2. As a consequence, we solve a weak version of an open problem posed in Gutin et al. (1998) [23], whose objective is to determine whether a 2-arc-colored tournament contains a properly arc-colored circuit. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Arc-colored digraphs Properly arc-colored paths/trails and circuits Hamiltonian directed path Arc-colored tournaments polynomial algorithms NP-completeness

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第1期185卷 105-121页

作者： Arslanov, M. Z. Ashigaliev, D. U. Ismail, E. E. Suleiman Demirel Univ Inst Problems Informat & Control Alma Ata 050010 Kazakhstan

In this paper the problem of optimally guillotine cutting a rectangle (A, B) into small rectangles of two kinds is considered. Rectangles of the first kind (c,a(i)), i is an element of I have the same width, and their heights can be various. Rectangles of the second kind (b(j),d), j is an element of J have the same height, and their widths can be various. The number of occurrences of each small rectangle in a cutting pattern is not restricted. Similar problems often appear in the furniture industry. This cutting problem is reduced to the shortest path problem in a special rectangular grid, for which a linear time algorithm is suggested. This approach generalizes the approach of [E. Girlich, A.G. Tarnowski, On polynomial solvability of two multiprocessor scheduling problems, Mathematical Methods of Operations Research 50 (1999) 27-51;A.G. Tarnowski, Advanced polynomial time algorithm for guillotine generalized pallet loading problem, in: The International Scientific Collection: Decision Making Under Conditions of Uncertainty (Cutting-Packing Problems), Ufa State Aviation Technical University, 1997, pp. 93-124] and allows us to construct polynomial algorithms for the guillotine cutting problem considered with a fixed number of small rectangles of two kinds. (c) 2007 Elsevier B.V. All rights reserved.

关键词： cutting shortest path problem polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

The Bernstein polynomial basis: A centennial retrospective

引用

COMPUTER AIDED GEOMETRIC DESIGN 2012年第6期29卷 379-419页

作者： Farouki, Rida T. Univ Calif Davis Dept Mech & Aerosp Engn Davis CA 95616 USA

One hundred years after the introduction of the Bernstein polynomial basis, we survey the historical development and current state of theory, algorithms, and applications associated with this remarkable method of representing polynomials over finite domains. Originally introduced by Sergei Natanovich Bernstein to facilitate a constructive proof of the Weierstrass approximation theorem, the leisurely convergence rate of Bernstein polynomial approximations to continuous functions caused them to languish in obscurity, pending the advent of digital computers. With the desire to exploit the power of computers for geometric design applications, however, the Bernstein form began to enjoy widespread use as a versatile means of intuitively constructing and manipulating geometric shapes, spurring further development of basic theory, simple and efficient recursive algorithms, recognition of its excellent numerical stability properties, and an increasing diversification of its repertoire of applications. This survey provides a brief historical perspective on the evolution of the Bernstein polynomial basis, and a synopsis of the current state of associated algorithms and applications. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Bernstein basis Weierstrass theorem polynomial approximation Bezier curves and surfaces Numerical stability polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Min-Max quickest path problems

引用

NETWORKS 2012年第4期60卷 253-258页

作者： Ruzika, Stefan Thiemann, Markus Univ Kaiserslautern D-67653 Kaiserslautern Germany

In a dynamic network, the quickest path problem asks for a path such that a given amount of flow can be sent from source to sink via this path in minimal time. In practical settings, for example, in evacuation or transportation planning, the problem parameters might not be known exactly a priori. It is therefore of interest to consider robust versions of these problems in which travel times and/or capacities of arcs depend on a certain scenario. In this article, minmax versions of robust quickest path problems are investigated and, depending on their complexity status, exact algorithms or fully polynomial-time approximation schemes are proposed. (c) 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 60(4), 253-258 2012

关键词： quickest path problem robust network flows optimization FPTAS polynomial algorithms multiple objective optimization

来源：评论

学校读者我要写书评

暂无评论

Some Results on Stable Sets for k-Colorable P₆-Free Graphs and Generalizations

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2012年第2期14卷 37-56页

作者： Mosca, Raffaele Univ G DAnnunzio Dipartimento Econ I-65127 Pescara Italy

This article deals with the Maximum Weight Stable Set (MWS) problem (and some other related NP-hard problems) and the class of P-6-free graphs. The complexity status of MWS is open for P-6-free graphs and is open even for P-5-free graphs (as a long standing open problem). Several results are known for MWS on subclasses of P-5-free: in particular, MWS can be solved for k-colorable P-5-free graphs in polynomial time for every k (depending on k) and more generally for (P-5, K-p)-free graphs (depending on p), which is a useful result since for every graph G one can easily compute a k-coloring of G, with k not necessarily minimum. This article studies the MWS problem for k-colorable P-6-free graphs and more generally for (P-6, K-p)-free graphs. Though we were not able to define a polynomial time algorithm for this problem for every k, this article introduces: (i) some structure properties of P-6-free graphs with respect to stable sets, (ii) two reductions for MWS on (P-6;K-p)-free graphs for every p, (iii) three polynomial time algorithms to solve MWS respectively for 3-colorable P-6-free, for 4-colorable P-6-free, and for (P-6, K-4)-free graphs (the latter allows one to state, together with other known results, that MWS can be solved for (P-6, F)-free graphs in polynomial time where F is any four vertex graph).

关键词： Maximum Weight stable Set problem P6-free graphs polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms

引用

DISCRETE APPLIED MATHEMATICS 2012年第6期160卷 697-707页

作者： Feder, Tomas Hell, Pavol Huang, Jing Rafiey, Arash Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Univ Victoria Dept Math & Stat Victoria BC V8W 3R4 Canada Ist Dalle Molle Intelligenza Artificiale CH-6928 Manno Lugano Switzerland

Interval graphs admit linear-time recognition algorithms and have several elegant forbidden structure characterizations. Interval digraphs can also be recognized in polynomial time, and they admit a characterization in terms of incidence matrices. Nevertheless, they do not have a known forbidden structure characterization or low-degree polynomial-time recognition algorithm. We introduce a new class of 'adjusted interval digraphs'. By contrast, for these digraphs we exhibit a natural forbidden structure characterization, in terms of a novel structure which we call an 'invertible pair'. Our characterization also yields a low-degree polynomial-time recognition algorithm of adjusted interval digraphs. It turns out that invertible pairs are also useful for undirected interval graphs, and our result yields a new forbidden structure characterization of interval graphs. In fact, it can be shown to be a natural link proving the equivalence of some known characterizations of interval graphs the theorems of Lekkerkerker and Boland, and of Fulkerson and Gross. In addition, adjusted interval digraphs naturally arise in the context of list homomorphism problems. If H is a reflexive undirected graph, the list homomorphism problem LHOM(H) is polynomial if H is an interval graph, and NP-complete otherwise. If H is a reflexive digraph, LHOM(H) is polynomial if H is an adjusted interval graph, and we conjecture that it is also NP-complete otherwise. We show that our results imply the conjecture in two important cases. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Interval graphs Interval digraphs Adjusted interval digraphs Forbidden structure characterizations polynomial algorithms List homomorphism problems Dichotomy

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：