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

Minimum cycle factors in quasi-transitive digraphs

DISCRETE OPTIMIZATION 2008年第1期5卷 121-137页

作者： Bang-Jensen, Jorgen Nielsen, Morten Hegner Univ Winnipeg Dept Math & Stat Winnipeg MB R3B 2E9 Canada Univ So Denmark Dept Math & Comp Sci DK-5230 Odense Denmark

We consider the minimum cycle factor problem: given a digraph D, find the mini mum number k(min)(D) of vertex disjoint cycles covering all vertices of D or verify that D has no cycle factor. There is an analogous problem for paths, known as the minimum path factor problem. Both problems are NP-hard for general digraphs as they include the Hamilton cycle and path problems, respectively. In 1994 Gutin [G. Gutin, polynomial algorithms for finding paths and cycles in quasi-transitive digraphs, Australas. J. Combin. 10 (1994) 231-236] proved that the minimum path factor problem is solvable in polynomial time, for the class of quasi-transitive digraphs, and so is the Hamilton cycle problem. As the minimum cycle factor problem is analogous to the minimum path factor problem and is a generalization of the Hamilton cycle problem, it is therefore a natural question whether this problem is also polynomially solvable, for quasi-transitive digraphs. We conjecture that the problem of deciding, for a fixed k, whether a quasi-transitive digraph D has a cycle factor with at most k cycles is polynomial, and we verify this conjecture for k = 3. We introduce the notion of an irreducible cycle factor and show how to convert a given cycle factor into an irreducible one in polynomial time when the input digraph is quasi-transitive. Finally, we show that even though this process will often reduce the number of cycles considerably, it does not always yield a minimum cycle factor. (C) 2007 Elsevier B.V. All rights reserved.

关键词： complementary cycles cycle factor quasi-transitive digraph network flow polynomial algorithm irreducible cycle factor

来源：评论

学校读者我要写书评

暂无评论

Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines

引用

BULLETIN OF THE POLISH ACADEMY OF SCIENCES-TECHNICAL SCIENCES 2017年第1期65卷 29-34页

作者： Furmanczyk, H. Kubale, M. Univ Gdansk Inst Informat Wita Stwosza 57 PL-80309 Gdansk Poland Gdansk Univ Technol Dept Algorithms & Syst Modelling Narutowicza 11-12 PL-80233 Gdansk Poland

In the paper we consider the problem of scheduling n identical jobs on 4 uniform machines with speeds s(1)>= s(2) >= s(3)>= s(4), respectively. Our aim is to find a schedule with a minimum possible length. We assume that jobs are subject to some kind of mutual exclusion constraints modeled by a bipartite incompatibility graph of degree Delta, where two incompatible jobs cannot be processed on the same machine. We show that the general problem is NP-hard even if s(1) = s(2) = s(3). If, however, Delta <= 4 ands(1)>= s(2) >= s(3)>= s(4), then the problem can be solved to optimality in time O(n(1.5)). The same algorithm returns a solution of value at most 2 times optimal provided that s(1) >= 2s(2). Finally, we study the case s(1)>= s(2) >= s(3) = s(4) and give a 32/15-approximation algorithm running also in O(n(1.5)) time.

关键词： equitable coloring NP-hardness polynomial algorithm scheduling uniform machine

来源：评论

学校读者我要写书评

暂无评论

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2017年第4期31卷 2348-2377页

作者： Cseh, Agnes Huang, Chien-Chung Kavitha, Telikepalli Hungarian Acad Sci H-1112 Budapest Hungary Corvinus Univ Budapest H-1112 Budapest Hungary Ecole Normale Super F-75005 Paris France Tata Inst Fundamental Res Sch Technol & Comp Sci Mumbai 400005 Maharashtra India

We are given a bipartite graph G - (A boolean OR B, E) where each vertex has a preference list ranking its neighbors: in particular, every a is an element of A ranks its neighbors in a strict order of preference, whereas the preference lists of b is an element of B may contain ties. A matching M is popular if there is no matching M ' such that the number of vertices that prefer M ' to M exceeds the number of vertices that prefer M to M '. We show that the problem of deciding whether G admits a popular matching or not is NP-hard. This is the case even when every b is an element of B either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each b is an element of B puts all its neighbors into a single tie. That is, all neighbors of b are tied in b 's list and b desires to be matched to any of them. Our main result is an O(n(2)) algorithm (where n=vertical bar A boolean OR B vertical bar) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in B have no preferences and do not care whether they are matched or not

关键词： popular matching NP-complete polynomial algorithm ties

来源：评论

学校读者我要写书评

暂无评论

A two-phase algorithm for solving a class of hard satisfiability problems

引用

OPERATIONS RESEARCH LETTERS 1998年第3-5期23卷 81-88页

作者： Warners, JP van Maaren, H CWI SEN2 NL-1090 GB Amsterdam Netherlands Delft Univ Technol Fac Informat Technol & Syst Dept Tech Math & Informat NL-2600 GA Delft Netherlands

The DIMACS suite of satisfiability (SAT) benchmarks contains a set of instances that are very hard for existing algorithms. These instances arise from learning the parity function on 32 bits. In this paper we develop a two-phase algorithm that is capable of solving these instances. In the first phase, a polynomially solvable subproblem is identified and solved. Using the solution to this problem, we can considerably restrict the size of the search space in the second phase of the algorithm, which is an extension of the well-known Davis-Putnam-Logemann-loveland algorithm. We conclude with reporting on our computational results on the parity instances. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： satisfiability polynomial algorithm Davis-Putnam algorithm

来源：评论

学校读者我要写书评

暂无评论

A new large-update interior point algorithm for P_*(κ) LCPs based on kernel functions

引用

APPLIED MATHEMATICS AND COMPUTATION 2006年第2期182卷 1169-1183页

作者： Cho, Gyeong-Mi Kim, Min-Kyung Dongseo Univ Div Comp & Informat Engn Dept Multimedia Engn Pusan 617716 South Korea Pusan Natl Univ Dept Math Pusan 609735 South Korea

In this paper we propose a new large-update primal-dual interior point algorithm for P,,(K) linear complementarity problems (LCPs). Recently, Peng et al. introduced self-regular barrier functions for primal-dual interior point methods (IPMs) for linear optimization (LO) problems and reduced the gap between the practical behavior of the algorithm and its theoretical worst case complexity. We introduce a new class of kernel functions which is not logarithmic barrier nor self-regular in the complexity analysis of interior point method (IPM) for P-*(kappa) linear complementarity problem (LCP). New search directions and proximity measures are proposed based on the kernel function. We showed that if a strictly feasible starting point is available, then the new large-update primal-dual interior point algorithms for solving P.(K) LCPs have the polynomial complexity O(q(3/2)(1+ 2 kappa) root n(log n)(q+1/q) log n/epsilon) which is better than the classical large-update primal-dual algorithm based on the classical logarithmic barrier function. (c) 2006 Elsevier Inc. All rights reserved.

关键词： large-update interior point method kernel function complexity polynomial algorithm linear complementarity problem

来源：评论

学校读者我要写书评

暂无评论

Packing triangles in low degree graphs and indifference graphs

引用

DISCRETE MATHEMATICS 2008年第8期308卷 1455-1471页

作者： Manic, Gordana Wakabayashi, Yoshiko Univ Sao Paulo Dept Ciencia Computacao BR-05508090 Sao Paulo Brazil

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

关键词： packing triangles approximation algorithm polynomial algorithm low degree graph indifference graph

来源：评论

学校读者我要写书评

暂无评论

From matchings to independent sets

引用

DISCRETE APPLIED MATHEMATICS 2017年 231卷 4-14页

作者： Lozin, Vadim Univ Warwick Math Inst Coventry CV4 7AL W Midlands England

In 1965, Jack Edmonds proposed his celebrated polynomial-time algorithm to find a maximum matching in a graph. It is well-known that finding a maximum matching in G is equivalent to finding a maximum independent set in the line graph of G. For general graphs, the maximum independent set problem is NP-hard. What makes this problem easy in the class of line graphs and what other restrictions can lead to an efficient solution of the problem? In the present paper, we analyse these and related questions. We also review various techniques that may lead to efficient algorithms for the maximum independent set problem in restricted graph families, with a focus given to augmenting graphs and graph transformations. Both techniques have been used in the solution of Edmonds to the maximum matching problem, i.e. in the solution to the maximum independent set problem in the class of line graphs. We survey various results that exploit these techniques beyond the line graphs. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Maximum matching Maximum independent set polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Emergency path restoration problems

引用

DISCRETE OPTIMIZATION 2012年第1期9卷 58-64页

作者： Averbakh, Igor Univ Toronto Scarborough Dept Management Scarborough ON M1C 1A4 Canada

We consider the problem of optimally scheduling the restoration of edges of a transportation network destroyed/damaged by a disaster. The restoration is performed by service units (servers) which have fixed restoration speeds. If several servers work simultaneously at the same point of the network, their collective restoration speed is the sum of their individual restoration speeds. The servers are initially located at some nodes. Each server can travel within the already restored part of the network with infinite speed, that is, at any time can immediately relocate to another point of the same connected component of the already restored part of the network. It is required to minimize a scheduling objective that can be expressed as the maximum or the sum of nondecreasing functions of the recovery times of the nodes, where the recovery time of a node is the time when the node is reached for the first time by a server. We present polynomial-time algorithms on path networks for problems with fixed initial locations of the servers. For problems with flexible locations that should also be optimized, we present polynomial-time algorithms for the case of equal restoration speeds of the servers, and prove that the problems are strongly NP-hard if the restoration speeds of the servers can be different. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Scheduling polynomial algorithm Network construction

来源：评论

学校读者我要写书评

暂无评论

A note on α-redundant vertices in graphs

引用

DISCRETE APPLIED MATHEMATICS 2001年第3期108卷 301-308页

作者： Brandstädt, A Lozin, VV Univ Rostock FB Informat D-18051 Rostock Germany Univ Nizhny Novgorod Nizhnii Novgorod 603600 Russia

A vertex v in a graph G is called alpha -redundant if alpha (G - v) = alpha (C), where alpha (G) stands for the stability number of G, i.e. the maximum size of a subset of pairwise nonadjacent vertices. We describe sufficient conditions for a vertex to be alpha -redundant in terms of some P-4 extensions. This leads to polynomial-time algorithms fur solving the stable set problem giving for an arbitrary input graph either the solution of the problem or a forbidden configuration such as an induced P-5 or an induced banner in the input graph. The algorithms extend and improve a number of previous results on the problem. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： stable set stability number polynomial algorithm alpha-redundant vertex P-4 extension

来源：评论

学校读者我要写书评

暂无评论

On stochastic lot-sizing problems with random lead times

引用

OPERATIONS RESEARCH LETTERS 2008年第3期36卷 303-308页

作者： Huang, Kai Kuecuekyavuz, Simge Tech Univ Eindhoven Dept Technol Management Sub Dept Operat Planning Accounting & Control NL-5600 MB Eindhoven Netherlands Univ Arizona Dept Syst & Ind Engn Tucson AZ 85721 USA

We give multi-stage stochastic programming formulations for lot-sizing problems where costs, demands and order lead times follow a general discrete-time stochastic process with finite support. We characterize the properties of an optimal solution and give a dynamic programming algorithm, polynomial in the scenario tree size, when orders do not cross in time. (C) 2008 Elsevier B.V. All rights reserved.

关键词： stochastic programming lot-sizing semi-Wagner-Whitin property polynomial algorithm random lead times

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：