Given two graphs H 1 and H 2 , a graph is (H1, H 2 )-free if it contains no induced subgraph isomorphic to H 1 nor H 2 . A dart is the graph obtained from a diamond by adding a new vertex and making it adjacent to exa...
详细信息
Given two graphs H 1 and H 2 , a graph is (H1, H 2 )-free if it contains no induced subgraph isomorphic to H 1 nor H 2 . A dart is the graph obtained from a diamond by adding a new vertex and making it adjacent to exactly one vertex with degree 3 in the diamond. In this paper, we show that there are finitely many k-vertex-critical (P5, dart)-free graphs for k >= 1. To prove these results, we use induction on k and perform a careful structural analysis via the Strong Perfect Graph Theorem combined with the pigeonhole principle based on the properties of vertex-critical graphs. Moreover, fork E { 5 , 6, 7} we characterize all k-vertex-critical (P5, dart)-free graphs using a computer generation algorithm. Our results imply the existence of a polynomial-time certifying algorithm to decide the k-colorability of (P5, dart)-free graphs fork >= 1 where the certificate is either a k-coloring or a (k+ 1)-vertex-critical induced subgraph. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
The maximum weight independent set problem (WIS), which is known to be generally NP-hard, admits polynomial-time solutions when restricted to graphs in some special classes. In particular, due to the celebrated Edmond...
详细信息
The maximum weight independent set problem (WIS), which is known to be generally NP-hard, admits polynomial-time solutions when restricted to graphs in some special classes. In particular, due to the celebrated Edmonds' matching algorithm, WIS is solvable in polynomialtime in the class of line graphs. This solution was extended to claw-free graphs and then further to fork- free graphs and to tclaw-free graphs, where tclaw is the graph consisting of t disjoint copies of the claw. The solution for tclaw-free graphs was obtained by generalizing Farber's approach to solve the problem for tK2-free graphs. In the present paper, we elaborate this approach further to develop a polynomial-time algorithm to solve the problem in the class of fork+tclaw-free graphs, generalizing both fork-free graphs and tclaw-free graphs, and in the class of P5 +tclaw-free graphs. We then apply the latter result to solve the more general problem of finding a d-regular induced subgraph of maximum weight in the class of P5 + tP3-free graphs in polynomialtime for any natural d and t, extending some of the previously known solutions.
Abstract:This paper addresses the problem of improving the optimal value of the Maximum Capacity Path(MCP)through expansion in a flexible network,and minimizing the involved *** only condition applied to the cost func...
详细信息
Abstract:This paper addresses the problem of improving the optimal value of the Maximum Capacity Path(MCP)through expansion in a flexible network,and minimizing the involved *** only condition applied to the cost functions is to be non-decreasing *** is a non-restrictive condition,reflecting the reality in practice,and is considered for the first time in the ***,the total cost of expansion is a combination of max-type cost(e.g.,for supervision)and sum-type cost(*** building infrastructures,price of materials,price of labor,etc.).For this purpose,two types of strategies are combined:(l)increasing the capacity of the existing arcs,and(l)adding potential new *** different problems are introduced and *** the problems have immediate applications in Internet routing *** first one is to extend the network,so that the capacity of an McP in the modified network becomes equal to a prescribed value,therefore the cost of modifications is minimized.A strongly polynomial-time algorithm is deduced to solve this *** second problem is a network expansion under a budget constraint,so that the capacity of an McP is maximized.A weakly polynomial-time algorithm is presented to deal with *** the special case when all the costs are linear,a Meggido's parametric search technique is used to develop an algorithm for solving the problem in strongly polynomial *** new approach has a time complexity of O(n^(4)),which is better than the time complexity of O(n4 log(n)of the previously known method from literature.
It is well known that every instance of the classical stable marriage problem admits at least one stable matching, and that such a matching can be found in O(n2) time by application of the Gale/Shapley algorithm. In t...
详细信息
It is well known that every instance of the classical stable marriage problem admits at least one stable matching, and that such a matching can be found in O(n2) time by application of the Gale/Shapley algorithm. In the classical version of the problem, each person must rank the members of the opposite sex in strict order of preference. In practical applications, a person may not wish (or be able) to choose between alternatives, thus allowing ties in the preference lists (or, more generally, allowing each preference list to be a partial order). With the introduction of such indifference, the notion of stability may be generalised in three obvious ways. For the weakest extension of stability, the same existence result holds, and essentially the same algorithm may be applied. In the other two cases, however, there is no guarantee that stable matchings exist. Nonetheless, in this paper, we describe polynomial-time algorithms that will establish, in either of these two cases, whether a matching of the appropriate kind exists, and if so will find such a matching.
We analyse a two-echelon discrete lot-sizing problem with a supplier and a retailer under information asymmetry. We assume that all cost parameters are time independent and that the retailer has single dimensional con...
详细信息
We analyse a two-echelon discrete lot-sizing problem with a supplier and a retailer under information asymmetry. We assume that all cost parameters are time independent and that the retailer has single dimensional continuous private information, namely either his setup cost or his holding cost. The supplier uses mechanism design to determine a menu of contracts that minimises his expected costs, where each contract specifies the retailer's procurement plan and a side payment to the retailer. There is no restriction on the number of contracts in the menu. To optimally solve this principal-agent contracting problem we present a two-stage approach, based on a theoretical analysis. The first stage generates a list of procurement plans that is sufficient to solve the contracting problem to optimality. The second stage optimally assigns these plans to the retailer types and determines all side payments. The result is an optimal menu with finitely many contracts that pools retailer types. We identify cases for which the contracting problem can be solved in polynomialtime and provide the corresponding algorithms. Furthermore, our analysis reveals that information asymmetry leads to atypical structures in the plans of the optimal menu, e.g., plans violating the zero-inventory property. Our solution approach and several results are directly applicable to more general problems as well. (C) 2018 Elsevier Ltd. All rights reserved.
Recently, optimal combinatorial algorithms have been presented for the energy minimization multiprocessor speed-scaling problem with migrations [5,7]. These algorithms use repeated maximum-flow computations that allow...
详细信息
Recently, optimal combinatorial algorithms have been presented for the energy minimization multiprocessor speed-scaling problem with migrations [5,7]. These algorithms use repeated maximum-flow computations that allow the partition of the set of jobs into subsets in which all the jobs are executed at the same speed. The optimality of these algorithms is based on a series of technical lemmas showing that this partition and the corresponding speeds lead to the minimization of the energy consumption. In this paper, we show that both the algorithms and their analysis can be greatly simplified. In order to do this, we formulate the problem as a convex cost flow problem in an appropriate flow network. Furthermore, we show that our approach is useful to solve other problems in the dynamic speed-scaling setting. As an example, we consider the preemptive open-shop speed-scaling problem and we propose a polynomial-time algorithm for finding an optimal solution based on the computation of convex cost flows. We also propose a polynomial-time algorithm for minimizing a linear combination of the sum of the completion times of the jobs and the total energy consumption, for the non-preemptive multiprocessor speed-scaling problem. Instead of using convex cost flows, our algorithm is based on the computation of a minimum weighted maximum matching in an appropriate bipartite graph. (C) 2015 Elsevier B.V. All rights reserved.
It is a well-established fact that routing metrics cannot be optimized via shortest path algorithms unless they are both monotone and isotonic. In particular, monotonicity guarantees the convergence of the shortest pa...
详细信息
It is a well-established fact that routing metrics cannot be optimized via shortest path algorithms unless they are both monotone and isotonic. In particular, monotonicity guarantees the convergence of the shortest path procedure, while isotonicity guarantees convergence to the optimal path. This paper presents a class of routing metrics that are not isotonic, yet can be solved to exact optimality via shortest path (or iterative shortest path) procedures. In particular, we consider routing metrics of the form "distance + 1/width" and "distance 'width", respectively, where the former is the default form of the composite metric of the interior gateway routing protocol (IGRP). To the best of our knowledge, for the first time we provide shortest-path-based algorithms that are guaranteed to minimize these metrics in spite of their non-isotonicity. This result implies that, contrary to common belief, the composite metric of the IGRP is in fact optimizable. (C) 2018 Elsevier B.V. All rights reserved.
Given a multihop wireless network and a source-destination pair of nodes, this paper addresses the problem of jointly selecting a communication route and allocating transmit power levels, so that the end-to-end spectr...
详细信息
Given a multihop wireless network and a source-destination pair of nodes, this paper addresses the problem of jointly selecting a communication route and allocating transmit power levels, so that the end-to-end spectral efficiency of the route exceeds a desired threshold. Spectral-efficient routing has been subject to interest in the recent literature. The transmit power level, however, has been assumed to be known, and route selection was considered in isolation. This paper presents the first rigourously proven optimal, polynomial-time algorithms for two versions of the joint spectral-efficient routing and power allocation problem: sum-power minimization and maximum power minimization. The proposed algorithms rely on the divide-and-conquer principle and the Bellman-Ford algorithm for shortest (or widest) path computation. Our computational results further illustrate the efficiency of the proposed approach.
This paper deals with the estimation of returns to scale (RTS) in free disposal hull (FDH) models and provides some stability intervals for preserving the RTS classification. It has been shown that the proposed stabil...
详细信息
This paper deals with the estimation of returns to scale (RTS) in free disposal hull (FDH) models and provides some stability intervals for preserving the RTS classification. It has been shown that the proposed stability intervals can be obtained via a polynomial-time algorithm based on the calculation of certain ratios of inputs and outputs, without solving any mathematical programming problem. The results of the study have been proved via some lemmas and theorems and have been illustrated by numerical examples and a real application. (c) 2008 Elsevier B.V. All rights reserved.
We consider the two-sided stable matching setting in which there may be uncertainty about the agents' preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery m...
详细信息
We consider the two-sided stable matching setting in which there may be uncertainty about the agents' preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model-for each agent, there is a probability distribution over linear preferences, (2) compact indifference model-for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model-there is a lottery over preference profiles. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. We also examine more restricted problems such as deciding whether a certainly stable matching exists. We find a rich complexity landscape for these problems, indicating that the form uncertainty takes is significant.
暂无评论