We investigate the scheduling problem on a single bounded parallel-batch machine where jobs belong to two non-disjoint agents (called agent A and agent B) and are of equal length but different size. Each job's siz...
详细信息
We investigate the scheduling problem on a single bounded parallel-batch machine where jobs belong to two non-disjoint agents (called agent A and agent B) and are of equal length but different size. Each job's size can be arbitrarily split into two parts and processed in the consecutive batches. It is permitted to process the jobs from different agents in a common batch. We show that it is unary NP-hard for the problem of minimizing the total weighted completion time of the jobs of agent A subject to the maximum cost of the jobs of agent B being upper bounded by a given threshold. For the case of the jobs of agent A having identical weights, we study the version of Pareto problem, and give a polynomial-time algorithm to generate all Pareto optimal points and a Pareto optimal schedule corresponding to each Pareto optimal point.
This paper considers a minimum spanning tree problem under the situation where costs for constructing edges in a network include both fuzziness and randomness. In particular, this article focuses on the case that the ...
详细信息
This paper considers a minimum spanning tree problem under the situation where costs for constructing edges in a network include both fuzziness and randomness. In particular, this article focuses on the case that the edge costs are expressed by random fuzzy variables. A new decision making model based on a possibility measure and a value at risk measure is proposed in order to find a solution which fully reflects random and fuzzy information. It is shown that an optimal solution of the proposed model is obtained by a polynomial-time algorithm. (C) 2012 Elsevier Ltd. All rights reserved.
Given a simple and undirected graph, nonnegative node weights, a nonnegative integer j, and a positive integer k, a k-matching in the graph is a subgraph with no isolated nodes and with maximum degree no more than k, ...
详细信息
Given a simple and undirected graph, nonnegative node weights, a nonnegative integer j, and a positive integer k, a k-matching in the graph is a subgraph with no isolated nodes and with maximum degree no more than k, a j-restricted k-matching is a k-matching with each connected component having at least j + 1 edges, and the total node weight of a j-restricted k-matching is the total weight of the nodes covered by the edges in the j-restricted k-matching. When j = 1 and k = 2, Kaneko [Kaneko A (2003) A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two. J. Combin. Theory, B 88:195-218] and Kano et al. [Kano M, Katona G, Kiraly Z (2005) Packing paths of length at least two. Discrete Math. 283:129-135] studied the problem of maximizing the number of nodes covered by the edges in a 1-restricted 2-matching. In this paper, we consider the problem of finding a j-restricted k-matching with the maximum total node weight. We present a polynomial-time algorithm for the problem as well as a min-max theorem in the case of j < k. We also prove that, when j >= k >= 2, the problem of maximizing the number of nodes covered by the edges in a j-restricted k-matching is NP-hard.
Given a preference system (G, <) and an integral weight function defined on the edge set of G (not necessarily bipartite), the maximum-weight stable matching problem is to find a stable matching of (G, <) with m...
详细信息
Given a preference system (G, <) and an integral weight function defined on the edge set of G (not necessarily bipartite), the maximum-weight stable matching problem is to find a stable matching of (G, <) with maximum total weight. In this paper we study this NP-hard problem using linear programming and polyhedral approaches. We show that the Rothblum system for defining the fractional stable matching polytope of (G, <) is totally dual integral if and only if this polytope is integral if and only if (G, <) has a bipartite representation. We also present a combinatorial polynomial-time algorithm for the maximum-weight stable matching problem and its dual on any preference system with a bipartite representation. Our results generalize Kiraly and Pap's theorem on the maximum-weight stable-marriage problem and rely heavily on their work.
A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The corresponding decision problem is called DISCONNECTED CUT. This problem is known to be NP-hard on general g...
详细信息
A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The corresponding decision problem is called DISCONNECTED CUT. This problem is known to be NP-hard on general graphs. We prove that it is polynomialtime solvable on claw-free graphs, answering a question of Ito et al. (TCS 2011). The basis for our result is a decomposition theorem for claw-free graphs of diameter 2, which we believe is of independent interest and builds on the research line initiated by Chudnovsky and Seymour (JCTB 2007-2012) and Hermelin et al. (ICALP 2011). On our way to exploit this decomposition theorem, we characterize how disconnected cuts interact with certain cobipartite subgraphs, and prove two further algorithmic results, namely that DISCONNECTED CUT is polynomial-time solvable on circular-arc graphs and line graphs. (C) 2020 Elsevier Inc. All rights reserved.
作者：
Malyshev, D. S.Natl Res Univ
Higher Sch Econ 25-12 Bolshaya Pecherskaya Ulitsa Nizhnii Novgorod 603155 Russia
We show that the weighted coloring problem can be solved for {P-5, banner}-free graphs and for {P-5, dart}-free graphs in polynomialtime on the sum of vertex weights. (C) 2018 Elsevier B.V. All rights reserved.
We show that the weighted coloring problem can be solved for {P-5, banner}-free graphs and for {P-5, dart}-free graphs in polynomialtime on the sum of vertex weights. (C) 2018 Elsevier B.V. All rights reserved.
A binary tree is regarded as a prefix-free binary code, in which the weighted sum of the lengths of root-leaf paths is equal to the expected codeword length. Huffman's algorithm computes an optimal tree in O(n log...
详细信息
A binary tree is regarded as a prefix-free binary code, in which the weighted sum of the lengths of root-leaf paths is equal to the expected codeword length. Huffman's algorithm computes an optimal tree in O(n log n) time, where n is the number of leaves. The problem was later generalized by allowing each leaf to have its own function of its depth and setting the sum of the function values as the objective function. The generalized problem was proved to be NP-hard. In this paper we study the case where every function is a unit step function, that is, a function that takes a lower constant value if the depth does not exceed a threshold, and a higher constant value otherwise. We show that for this case, the problem can be solved in O(n log n) time, by reducing it to the Coin Collector's problem.
We study two generalised stable matching problems motivated by the current matching scheme used in the higher education sector in Hungary. The first problem is an extension of the College Admissions problem in which t...
详细信息
We study two generalised stable matching problems motivated by the current matching scheme used in the higher education sector in Hungary. The first problem is an extension of the College Admissions problem in which the colleges have lower quotas as well as the normal upper quotas. Here, we show that a stable matching may not exist and we prove that the problem of determining whether one does is NP-complete in general. The second problem is a different extension in which, as usual, individual colleges have upper quotas, but, in addition, certain bounded subsets of colleges have common quotas smaller than the sum of their individual quotas. Again, we show that a stable matching may not exist and the related decision problem is NP-complete. On the other hand, we prove that, when the bounded sets form a nested set system, a stable matching can be found by generalising, in non-trivial ways, both the applicant-oriented and college-oriented versions of the classical Gale-Shapley algorithm. Finally, we present an alternative view of this nested case using the concept of choice functions, and with the aid of a matroid model we establish some interesting structural results for this case. (C) 2010 Elsevier B.V. All rights reserved.
作者：
Malyshev, D. S.Natl Res Univ
Higher Sch Econ 25-12 Bolshaja Pecherskaja Ulitsa Nizhnii Novgorod 603155 Russia
We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a ...
详细信息
We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.
The coloring problem is studied in the paper for graph classes defined by two small forbidden induced subgraphs. We prove some sufficient conditions for effective solvability of the problem in such classes. As their c...
详细信息
The coloring problem is studied in the paper for graph classes defined by two small forbidden induced subgraphs. We prove some sufficient conditions for effective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most five vertices except 13 explicitly enumerated cases.
暂无评论