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

Some observations on maximum weight stable sets in certain P₅-free graphs

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第3期184卷 849-859页

作者： Mosca, Raffaele Univ Studi G d Annunzio Dipartimento Sci I-65127 Pescara Italy

The maximum weight stable set problem (MWS) is the weighted version of the maximum stable set problem (MS), which is NP-hard. The class of P-5-free graphs - i.e., graphs with no induced path of five vertices - is the unique minimal class, defined by forbidding a single connected subgraph, for which the computational complexity of MS is an open question. At the same time, it is known that NIS can be efficiently solved for (P-5, F) -free graphs, where F is any graph of five vertices different to a C-5. In this paper we introduce some observations on P-5-free graphs, and apply them to introduce certain subclasses of such graphs for which one can efficiently solve MWS. That extends or improves some known results, and implies - together with other known results - that MWS can be efficiently solved for (P-5, F) -free graphs where F is any graph of five vertices different to a C-5. (C) 2006 Elsevier B.V. All rights reserved.

关键词： maximum weight stable set problem P-5-free graphs polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

NP-hard and polynomial cases for the single-item lot sizing problem with batch ordering under capacity reservation contract

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第2期257卷 483-493页

作者： Akbalik, Ayse Hadj-Alouane, Atidel B. Sauer, Nathalie Ghribi, Houcem Univ Lorraine Lab LGIPM F-57012 Metz France Univ Tunis El Manar Ecole Natl Ingn Tunis OASIS BP 37 Le Belvedere Tunis 1002 Tunisia

In this paper, we study the single-item lot sizing problem under a capacity reservation contract. A manufacturer is replenished by an external supplier with batch deliveries and a certain capacity is reserved at the supplier level with an advantageous cost. In addition to the classical ordering and inventory holding costs, for each batch ordered under the reserved capacity a fixed cost per batch is incurred;and for batches exceeding this capacity a higher fixed cost per batch is paid, typically through the purchase from the spot market. We identify various NP-hard cases, propose a pseudo-polynomial time dynamic programming algorithm under arbitrary parameters, show that the problem admits an FPTAS and give polynomial time algorithms for special cases. We finally state a list of open problems for further research. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Inventory Lot sizing Capacity reservation contract Complexity polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Injective coloring of some subclasses of bipartite graphs and chordal graphs

引用

DISCRETE APPLIED MATHEMATICS 2021年 291卷 68-87页

作者： Panda, B. S. Priyamvada Indian Inst Technol Delhi Dept Math New Delhi 110016 India

A vertex coloring of a graph G = (V, E) that uses k colors is called an injective k-coloring of G if no two vertices having a common neighbor have the same color. The minimum k for which G has an injective k-coloring is called the injective chromatic number of G. Given a graph G and a positive integer k, the DECIDE INJECTIVE COLORING PROBLEM iS to decide whether G admits an injective k-coloring. It is known that DECIDE INJECTIVE COLORING PROBLEM is NP-complete for bipartite graphs. In this paper, we strengthen this result by showing that this problem remains NP-complete for perfect elimination bipartite graphs, star-convex bipartite graphs and comb-convex bipartite graphs, which are proper subclasses of bipartite graphs. Moreover, we show that for every epsilon > 0, it is not possible to efficiently approximate the injective chromatic number of a perfect elimination bipartite graph within a factor of n(1/3-epsilon) unless ZPP = NP. On the positive side, we propose a linear time algorithm for biconvex bipartite graphs and O(nm) time algorithm for convex bipartite graphs for finding the optimal injective coloring. We prove that the injective chromatic number of a chordal bipartite graph can be determined in polynomial time. It is known that DECIDE INJECTIVE COLORING PROBLEM is NP-complete for chordal graphs. We give a linear time algorithm for computing the injective chromatic number of proper interval graphs, which is a proper subclass of chordal graphs. DECIDE INJECTIVE COLORING PROBLEM is also known to be NP-complete for split graphs. We show that DECIDE INJECTIVE COLORING PROBLEM remains NP-complete for K-1,K-t-free split graphs for t >= 4 and polynomially solvable for t <= 3. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Injective coloring polynomial time algorithm NP-complete Inapproximability Graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Double vertex-edge domination in graphs: complexity and algorithms

引用

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2021年第1-2期66卷 245-262页

作者： Naresh Kumar, H. Pradhan, D. Venkatakrishnan, Y. B. SASTRA Deemed Univ Dept Math Thanjavur India Indian Inst Technol ISM Dept Math & Comp Dhanbad Bihar India

In a graph G = (V, E), a vertex v is an element of V is said to ve-dominate the edges incident on v as well as the edges adjacent to these incident edges on v. A set D subset of V is called a double vertex-edge dominating set if every edge of the graph is ve-dominated by at least two vertices of D. Given a graph G, the double vertex-edge dominating problem, namely Min-DVEDS is to find a minimum double vertex-edge dominating set of G. In this paper, we show that the decision version of Min-DVEDS is NP-complete for chordal graphs. We present a linear time algorithm to find a minimum double vertexedge dominating set in proper interval graphs. We also show that for a graph having n vertices, Min-DVEDS cannot be approximated within (1 - epsilon) ln n for any epsilon > 0 unless NP subset of Dtime(n(O(log log n))). On positive side, we show that Min-DVEDS can be approximated by a factor of O(ln Delta). Finally, we show that Min-DVEDS is APX-complete for graphs with maximum degree 5.

关键词： Domination Vertex-edge domination Double vertex-edge domination polynomial time algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

THE GENERALIZED TERMINAL BACKUP PROBLEM

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第3期29卷 1764-1782页

作者： Bernath, Attila Kobayashi, Yusuke Matsuoka, Tatsuya Eotvos Lorand Univ Dept Operat Res MTA ELTE Egervary Res Grp Budapest Hungary Univ Tsukuba Tsukuba Ibaraki 3058573 Japan Univ Tokyo Tokyo 1138656 Japan

We consider the following network design problem that we call the Generalized Terminal Backup Problem: given a graph (or a hypergraph) G(0) = (V, E-0), a set of (at least 2) terminals T subset of V, and a requirement r(t) for every t is an element of T, find a multigraph G = (V, E) such that lambda G(0)+ G(t, T - t) >= r(t) for any t is an element of T. In the minimum cost version the objective is to find G minimizing the total cost c(E) = Sigma(uv is an element of E) c(uv), given also costs c(uv) >= 0 for every pair u, v is an element of V. In the degree-specified version the question is to decide whether such a G exists, satisfying that the degree of v is an element of V is a prescribed value m(v). The Terminal Backup Problem solved in [E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678-708] is the special case where G(0) is the empty graph and r(t) = 1 for every terminal t is an element of T. We solve the Generalized Terminal Backup Problem in the following two cases. In the first case we solve the degree-specified version by a splitting-off theorem. This splitting-off theorem in turn provides the solution for the minimum cost version in the case when c is node-induced, that is c(uv) = w(u) + w(v) for some node weights w : V -> R+. In the second case we turn to the general minimum cost version, and we are able to solve it when G0 is the empty graph. This includes the Terminal Backup Problem (r = 1) and the Maximum-Weight b-matching Problem (T = V). The solution depends on an interesting new variant of a theorem of Lovasz and Cherkassky, and on the solution of the so-called Simplex Matching Problem. Our algorithms run in polynomial time for both problems.

关键词： connectivity augmentation problem survivable network design problem polynomial time algorithm skew-supermodular function

来源：评论

学校读者我要写书评

暂无评论

Spanning subgraphs of graphs partitioned into two isomorphic pieces

引用

JOURNAL OF GRAPH THEORY 2006年第2期51卷 123-136页

作者： Bonato, A Wilfrid Laurier Univ Dept Math Waterloo ON N2L 3C5 Canada

A graph has the neighbor-closed-co-neighbor, or ncc property, if for each of its vertices x, the subgraph induced by the neighbor set of x is isomorphic to the subgraph induced by the closed non-neighbor set of x. As proved by Bonato and Nowakowski [5], graphs with the ncc property are characterized by the existence of perfect matchings satisfying certain local conditions. In the present article, we investigate the spanning subgraphs of ncc graphs, which we name sub-ncc. Several equivalent characterizations of finite sub-ncc graphs are given, along with a polynomial time algorithm for their recognition. The infinite sub-ncc graphs are characterized, and we demonstrate the existence of a countable universal sub-ncc graph satisfying a strong symmetry condition called pseudo-homogeneity. (c) 2005 Wiley Periodicals, Inc.

关键词： spanning subgraph ncc graph matching local property polynomial time algorithm pseudo-homogeneous graph

来源：评论

学校读者我要写书评

暂无评论

Equilibria for Joint Congestion Game With Destination and Route Choices

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2024年第12期25卷 21267-21277页

作者： Tan, Heqing Chen, Anthony Xu, Xiangdong Tongji Univ Key Lab Rd & Traff Engn Minist Educ Shanghai 201804 Peoples R China Hong Kong Polytech Univ Dept Civil & Environm Engn Hong Kong Peoples R China

We extend congestion games to the setting where players need to make multiple joint choices with interactions in a hierarchical manner (termed joint congestion game). At each choice dimension, players are involved in a typical congestion game. This game has a feature that the output of one choice dimension serves as an input of another one, and the costs paid by players in different choice dimensions are interdependent. Focusing on the joint congestion game with destination and route choices (i.e., select which destination and which route to complete a trip), we show the existence and uniqueness of the Nash equilibrium under mild assumptions in a nonatomic game setting. Then we investigate the property of the general quantal response equilibrium (QRE) for the joint congestion game in which players have perception errors of their costs (characterized by a probabilistic distribution). The QRE condition for the joint congestion game is further extended to the case where the analyst has only incomplete information about players' perceived costs. A specific cross moment QRE model using the mean and covariance information is accordingly developed to account for both the analyst's and players' imperfect information/perception. We present an equivalent convex program that promises a unique solution for the cross moment QRE model, and provide a polynomial algorithm to solve it. Numerical results illustrate the features of the developed model for the joint congestion game and demonstrate the efficiency of the solution algorithm on two realistic transportation networks.

关键词： Joint congestion game quantal response equilibrium cross moment polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Envy-Free Matchings with Lower Quotas

引用

algorithmICA 2020年第2期82卷 188-211页

作者： Yokoi, Yu Natl Inst Informat Tokyo 1018430 Japan

While every instance of the Hospitals/Residents problem admits a stable matching, the problem with lower quotas (HR-LQ) has instances with no stable matching. For such an instance, we expect the existence of an envy-free matching, which is a relaxation of a stable matching preserving a kind of fairness property. In this paper, we investigate the existence of an envy-free matching in several settings, in which hospitals have lower quotas and not all doctor-hospital pairs are acceptable. We first provide an algorithm that decides whether a given HR-LQ instance has an envy-free matching or not. Then, we consider envy-freeness in the Classified Stable Matching model due to Huang (in: Procedings of 21st annual ACM-SIAM symposium on discrete algorithms (SODA2010), SIAM, Philadelphia, pp 1235-1253, 2010), i.e., each hospital has lower and upper quotas on subsets of doctors. We show that, for this model, deciding the existence of an envy-free matching is NP-hard in general, but solvable in polynomial time if quotas are paramodular.

关键词： Stable matchings Envy-free matchings Lower quotas polynomial time algorithm Paramodular functions

来源：评论

学校读者我要写书评

暂无评论

OPTIMIZING THE SYSTEM OF VIRTUAL PATHS

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 1994年第6期2卷 581-587页

作者： CHLAMTAC, I FARAGO, A ZHANG, T Dept. of Electr. & Comput. Eng. Massachusetts Univ. Amherst MA USA

The virtual path (VP) concept is known to be a powerful transport mechanism for ATM networks. This paper deals with the optimization of the virtual paths system from a bandwidth utilization perspective. While previous research on VP management has basically assumed that bandwidth in ATM networks is unlimited, emerging technologies and applications are changing this premise. In many networks, such as wireless, bandwidth is always at a premium. In wired networks, with increasing user access speeds, less than a dozen of broadband connections can saturate even a Gigabit link. In this paper we present an efficient algorithm that finds a system of VP routes for a given set of VP terminators and VP capacity demands. This solution is motivated by the need to minimize the load, or reduce congestion, generated by the VP's on individual links. A nontrivial performance guarantee is proven for the quality of the proposed solution and numerical results show that the proposed solution carries the potential for a near optimal allocation of VP's.

关键词： Asynchronous Transfer Mode B ISDN Telecommunication Network Routing Telecommunication Network Management Performance Evaluation Channel Capacity Telecommunication Links Virtual Path Management Transport Mechanism ATM Networks Optimization Virtual Paths System Bandwidth Utilization Wireless Networks Wired Networks User Access Speeds Broadband Connections Gigabit Link VP Routes VP Terminators VP Capacity Demands Congestion Performance Guarantee Optimal Allocation B ISDN polynomial time algorithm Link Capacity Asynchronous Transfer Mode Bandwidth Optical Fiber Networks Personal Communication Networks Technology Management Power System Management B ISDN Switching Circuits Optical Network Units time Factors

来源：评论

学校读者我要写书评

暂无评论

Structural Grobner basis detection

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 1997年第4期8卷 257-263页

作者： Sturmfels, B Wiegelmann, M UNIV CALIF BERKELEY DEPT MATHBERKELEYCA 94720 UNIV TRIER FACHBEREICH MATHD-54286 TRIERGERMANY

We determine the computational complexity of deciding whether m polynomials in n variables have relatively prime leading terms with respect to some term order. This problem in NP-complete in general, but solvable in polynomial time in two different situations, when m is fixed and when n - m is fixed. Our new algorithm for the second case determines a candidate set of leading terms by solving a maximum matching problem. This reduces the problem to linear programming.

关键词： Grobner basis variation of term orders NP-completeness polynomial time algorithm system of polynomial equations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：