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

An algorithm for finding a maximum t-matching excluding complete partite subgraphs

DISCRETE OPTIMIZATION 2012年第2期9卷 98-108页

作者： Kobayashi, Yusuke Yin, Xin Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138656 Japan Stanford Univ Inst Computat & Math Engn Stanford CA 94305 USA

For an integer t and a Fixed graph H, we consider the problem of Finding a maximum t-matching not containing H as a subgraph, which we call the H-free t-matching problem. This problem is a generalization of the problem of finding a maximum 2-matching with no short cycles, which has been well-studied as a natural relaxation of the Hamiltonian circuit problem. When H is a complete graph Kt+1 or a complete bipartite graph K-t,K-t, in 2010, Berczi and Vegh gave a polynomial-time algorithm for the H-free t-matching problem in simple graphs with maximum degree at most t + 1. A main contribution of this paper is to extend this result to the case when H is a t-regular complete partite graph. We also show that the problem is NP-complete when H is a connected t-regular graph that is not complete partite. Since it is known that, for a connected t-regular graph H, the degree sequences of all H-free t-matchings in a graph form a jump system if and only if H is a complete partite graph, our results show that the polynomial-time solvability of the H-free t-matching problem is consistent with this condition. (C) 2012 Elsevier B.V. All rights reserved.

关键词： b-matching Complete partite graph polynomial-time algorithm Shrinking

来源：评论

学校读者我要写书评

暂无评论

A lexicographic optimization approach to the deviation-flow refueling station location problem on a general network

引用

OPTIMIZATION LETTERS 2022年第3期16卷 953-982页

作者： Abbaas, Omar Ventura, Jose A. Penn State Univ Harold & Inge Marcus Dept Ind & Mfg Engn University Pk PA 16802 USA

The problem of setting up an Alternative Fuel (AF) refueling infrastructure along traffic networks is gaining more interest as AF powered vehicles are becoming more popular due to environmental and economic reasons. This study addresses the refueling station location problem with allowed deviations on a general network. The primary objective is to maximize the amount of flow covered by a given number of stations. Unlike the common practice of having a predetermined set of candidate station locations that may not necessarily hold an optimal solution, this study considers the characteristics of the traffic network and vehicle driving range to discretize the continuous version of the problem and select a finite set of candidate locations that guarantees optimality. This is done by finding the greatest common divisor, g, of the lengths of all edges in the network and half of the vehicle driving range. We prove that there is always an optimal solution where all refueling stations are located at distances that are integer multiples of g from network vertices. This result is used to define refueling sets along the network. The endpoints of these sets are then considered as candidate locations. A secondary objective is introduced to minimize the total travel distance of covered flows. This bi-objective approach does not only optimize the utility of available resources by maximizing covered flows, but also improves convenience, lowers travel cost, and reduces greenhouse gas emissions by minimizing the total travel distance. Finally, a numerical example is provided to illustrate the proposed methods.

关键词： Refueling infrastructure Alternative fuels Symmetric traffic network Path deviation Edge scanning Global optimality polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A unified approach for scheduling with convex resource consumption functions using positional penalties

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第2期206卷 301-312页

作者： Leyvand, Yaron Shabtay, Dvir Steiner, George McMaster Univ DeGroote Sch Business Operat Management Area Hamilton ON Canada Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel

We provide a unified model for solving single machine scheduling problems with controllable processing times in polynomial time using positional penalties. We show how this unified model can be useful in solving three different groups of scheduling problems. The first group includes four different due date assignment problems to minimize an objective function which includes costs for earliness, tardiness, due date assignment, makespan and total resource consumption. The second group includes three different due date assignment problems to minimize an objective function which includes the weighted number of tardy jobs, due date assignment costs, makespan and total resource consumption costs. The third group includes various scheduling problems which do not involve due date assignment decisions. We show that each of the problems from the first and the third groups can be reduced to a special case of our unified model and thus can be solved in O(n(3)) time. Furthermore, we show how the unified model can housed repeatedly as a subroutine to solve all problems from the second group in O(n(4)) time. In addition, we also show that faster algorithms exist for several special cases. Crown Copyright (C) 2010 Published by Elsevier B.V. All rights reserved.

关键词： Single machine scheduling Controllable processing times Resource allocation Due date assignment Positional penalties polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A quadratic time algorithm for computing the optimal landing times of a fixed sequence of planes

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第3期270卷 1148-1157页

作者： Faye, Alain ENSILE Lab CEDRIC 1 Sq Resistance F-91025 Evry France

This paper considers the Aircraft Landing Problem. The aim is to schedule arriving aircraft at the airport under the condition of safe landing. Landing times lie within predefined time windows and safety separation constraints between two successive aircraft landing on the same runway, must be satisfied. The objective is to minimize the total cost of landing deviation from predefined target times within the time windows. On each runway, for a fixed landing sequence, the problem can be solved by a linear program. When safety separation times satisfy the Triangle Inequality, we propose an O(n(2)) algorithm for solving the problem where n is the number of planes of the sequence. We compare the performance of this polynomial time algorithm to the linear programming method. The two methods are embedded in an iterative algorithm, based on simulated annealing, for solving the single runway case. Computational tests, performed on publicly available problems, show that the heuristic based on our algorithm is much faster than the one using linear programming. This gain in CPU time allows to obtain better solutions in a fixed amount of time. (C) 2018 Elsevier B.V. All rights reserved.

关键词： OR in airlines Aircraft Landing Problem Landing times Dynamic programming polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On decomposability of Multilinear sets

引用

MATHEMATICAL PROGRAMMING 2018年第2期170卷 387-415页

作者： Del Pia, Alberto Khajavirad, Aida Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA Univ Wisconsin Wisconsin Inst Discovery Madison WI 53706 USA Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA

We consider the Multilinear set defined as the set of binary points (x, y) satisfying a collection of multilinear equations of the form , , where denotes a family of subsets of of cardinality at least two. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is possible when is decomposable into simpler Multilinear sets ,;namely, the convex hull of can be obtained by convexifying each , separately. In this paper, we study the decomposability properties of Multilinear sets. Utilizing an equivalent hypergraph representation for Multilinear sets, we derive necessary and sufficient conditions under which is decomposable into , , based on the structure of pair-wise intersection hypergraphs. Our characterizations unify and extend the existing decomposability results for the Boolean quadric polytope. Finally, we propose a polynomial-time algorithm to optimally decompose a Multilinear set into simpler subsets. Our proposed algorithm can be easily incorporated in branch-and-cut based global solvers as a preprocessing step for cut generation.

关键词： Multilinear functions Convex hull Decomposition Zero-one polynomial optimization Factorable relaxations polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Combinatorics and algorithms for Quasi-Chain Graphs

引用

algorithmICA 2023年第3期85卷 642-664页

作者： Alecu, Bogdan Atminas, Aistis Lozin, Vadim Malyshev, Dmitriy Univ Leeds Sch Comp Leeds W Yorkshire England Xian Jiaotong Liverpool Univ Dept Math Sci 111 Renai Rd Suzhou 215123 Peoples R China Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Natl Res Univ Lab Algorithms & Technol Networks Anal Higher Sch Econ 136 Rodionova Str Nizhnii Novgorod 603093 Russia

The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. This latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded in it. In the present paper, we show that the universe of quasi-chain graphs is at least as complex as the universe of permutations by establishing a bijection between the class of all permutations and a subclass of quasi-chain graphs. This implies, in particular, that the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs. On the other hand, we propose a decomposition theorem for quasi-chain graphs that implies an implicit representation for graphs in this class and efficient solutions for some algorithmic problems that are generally intractable.

关键词： Bipartite graphs Implicit representation polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Independent sets in extensions of 2K₂-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2005年第1期146卷 74-80页

作者： Lozin, VV Mosca, R Rutgers State Univ RUTCOR Piscataway NJ 08854 USA Univ G dAnnunzio Dipartimento Sci I-65127 Pescara Italy

The class of 2K(2)-free graphs includes several interesting subclasses such as split, pseudo-split, threshold graphs, complements to chordal, interval or trivially perfect graphs. The fundamental property of 2K(2)-free graphs is that they contain polynomially many maximal independent sets. As a consequence, several important problems that are NP-hard in general graphs, such as 3-colorability, maximum weight independent set (WIS), minimum weight independent dominating set (WID), become polynomial-time solvable when restricted to the class of 2K(2)-free graphs. In the present paper, we extend 2K(2)-free graphs to larger classes with polynomial-time solvable WIS or WID. In particular, we show that WIS can be solved in polynomial time for (K-2 + K-1,K-3)-free graphs and WID for (K-2 + K-1.2)-free graphs. The latter result is in contrast with the fact that independent domination is NP-hard in the class of 2K(1.2)-free graphs, which has been recently proven by Zverovich. (C) 2004 Elsevier B.V. All rights reserved.

关键词： maximal stable set polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Computing lower bounds on functional units before scheduling

引用

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS 1996年第2期4卷 273-279页

作者： Chaudhuri, S Walker, RA RENSSELAER POLYTECH INST DEPT ELECT COMP & SYST ENGNTROYNY 12180 RENSSELAER POLYTECH INST DEPT COMP SCITROYNY 12180

This brief presents a new polynomial-time algorithm for computing lower bounds on the number of functional units (FU's) of each type required to schedule a data Bow graph in a specified number of control steps. A formal approach is presented that is guaranteed to find the tightest possible bounds that can be found by relaxing either the precedence constraints or integrality constraints on the scheduling problem, This tight, yet fairly efficient, bounding method can be used to estimate FU area, to generate resource constraints for reducing the search space, or in conjunction with exact techniques for efficient optimal design space exploration.

关键词： VLSI circuit CAD data flow graphs formal specification high level synthesis integrated circuit design scheduling VLSI synthesis data flow graph scheduling functional units lower bounds optimal design space exploration polynomial-time algorithm resource c Lower bound FUNCTIONAL UNITS circuit CAD integrated circuit design Very large scale integration Formal specifications data flow graphs high level synthesis

来源：评论

学校读者我要写书评

暂无评论

Flow shop scheduling problems under machine-dependent precedence constraints

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2004年第1期8卷 13-28页

作者： Gladky, AA Shafransky, YM Strusevich, VA Natl Acad Sci Belarus Inst Engn Cybernet Minsk BELARUS Univ Greenwich Sch Comp & Math Sci London SE18 6PF England

The paper considers the flow shop scheduling problems to minimize the makespan, provided that an individual precedence relation is specified on each machine. A fairly complete complexity classification of problems wit... 详细信息

关键词： flow shop precedence constraints complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient domination for classes of P₆-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2017年 223卷 15-27页

作者： Brandstaedt, Andreas Eschen, Elaine M. Friese, Erik Karthick, T. Univ Rostock Fachbereich Informat A Einstein Str 22 D-18051 Rostock Germany West Virginia Univ Lane Dept CSEE Morgantown WV 26506 USA Univ Rostock Fachbereich Math Ulmenstr 69 D-18057 Rostock Germany Indian Stat Inst Comp Sci Unit Chennai Ctr Madras 600113 Tamil Nadu India

In a finite undirected graph G, a vertex dominates itself and all its neighbors in G. A vertex set D is an efficient dominating set (e.d. 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. in G, is known to be NP-complete even for very restricted graph classes such as P-7-free chordal graphs;its complexity was an open question for P-6-free graphs and was open even for the subclass of P-6-free chordal graphs. Recently, Lokshtanov et al., and independently, Brandstadt and Mosca showed that ED is solvable in polynomial time for P-6-free graphs. The ED problem on a graph G can be reduced to the Maximum Weight Independent Set problem on the square of G. In this paper, we show that squares of P-6-free chordal graphs that have an e.d. are chordal;this, even holds for the larger class of (P-6, house, hole, domino)-free graphs. Thus, ED/WeightedED is solvable in polynomial time for (P-6, house, hole, domino)-free graphs, and in particular, for P-6-free chordal graphs. Also, the time bound achieved for ED on this class is much better than in the P-6-free case. Moreover, we show that squares of P-6-free graphs that have an e.d. are hole-free. Based on this result, we show that ED is solvable in polynomial time for (P-6, net)-free graphs;again, the time bound for ED on this class is much better than in the P-6-free case. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Efficient domination P-6-free graphs Chordal graphs Hole-free graphs (House, hole, domino)-free graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：