作者：
Malyshev, D. S.Natl Res Univ
Higher Sch Econ 25-12 Bolshaja Pecherskaja Ulitsa Nizhnii Novgorod 603155 Russia
The complexity of the coloring problem is known for all hereditary classes defined by two connected 5-vertex forbidden induced subgraphs except 13 cases. We update this result by proving polynomial-time solvability of...
详细信息
The complexity of the coloring problem is known for all hereditary classes defined by two connected 5-vertex forbidden induced subgraphs except 13 cases. We update this result by proving polynomial-time solvability of the problem for two of the mentioned 13 classes.
In this paper, we present a simple polynomial-time algorithm solving the shortest multipaths problem in particular grid graphs called dense channels. Our work extends the results of Formann et al. [M. Formann, D. Wagn...
详细信息
In this paper, we present a simple polynomial-time algorithm solving the shortest multipaths problem in particular grid graphs called dense channels. Our work extends the results of Formann et al. [M. Formann, D. Wagner, F. Wagner, Routing through a dense channel with minimum total wire length, Journal of algorithms 15 (1993) 267-283], by considering arbitrary horizontal and vertical capacities. (c) 2006 Elsevier B.V. All rights reserved.
This paper deals with minimum spanning tree problems where each edge weight is a fuzzy random variable. In order to consider the imprecise nature of the decision maker's judgment, a fuzzy goal for the objective fu...
详细信息
This paper deals with minimum spanning tree problems where each edge weight is a fuzzy random variable. In order to consider the imprecise nature of the decision maker's judgment, a fuzzy goal for the objective function is introduced. A novel decision making model is constructed based on possibility theory and on a stochastic programming model. It is shown that the problem including both randomness and fuzziness is reduced to a deterministic equivalent problem. Finally, a polynomial-time algorithm is provided to solve the problem.
We consider the problem of moving a connected set of railcars, which we refer to as a train, from an origin layout to a destination layout in a railyard, accounting for the special structure of the railyard network an...
详细信息
We consider the problem of moving a connected set of railcars, which we refer to as a train, from an origin layout to a destination layout in a railyard, accounting for the special structure of the railyard network and the length and orientation of the train. We propose a novel shortest path algorithm for determining a sequence of moves that minimizes the total distance (and associated time) required to move a train from its origin to destination. A railyard network consists of a set of track sections connected via switch points, which correspond to points at which three sections of track come together, such that one pair of the track segments forms an acute angle (and the other two pairs form obtuse angles). A train's ability to traverse a switch node depends on the train's length and whether or not its desired route involves traversing the acute angle or an obtuse angle at the switch. The shortest route problem for a train is further complicated by the fact that a train's position on the network at any point in time may span multiple nodes in the network. We propose an easily explained solution approach that addresses the complications associated with switch points and the train's length to determine a shortest route from origin to destination in O(e + n log n) operations, where n and e correspond to the number of switch nodes and edges in the network respectively.
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs,...
详细信息
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems all remain NP-hard or coNP-hard when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques? On the positive side, we show that the following three problems whose computational complexity is open in general can be solved in polynomialtime in the class of diamondfree graphs: Does every induced subgraph have a strong clique? Is every maximal clique strong? Is every edge contained in a strong clique? The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erd os-Hajnal property for such graphs. (c) 2020 Elsevier B.V. All rights reserved.
Three algorithms of Gram Schmidt type are given that produce orthogonal decompositions of finite d-dimensional symmetric, alternating, or Hermitian forms over division rings. The first uses d(3)/3 + O(d(2)) products i...
详细信息
Three algorithms of Gram Schmidt type are given that produce orthogonal decompositions of finite d-dimensional symmetric, alternating, or Hermitian forms over division rings. The first uses d(3)/3 + O(d(2)) products in Delta. Next, that algorithm is adapted in two new directions. One is a nearly optimal sequential algorithm whose complexity matches the complexity of matrix multiplication. The other is a parallel algorithm. (C) 2013 Elsevier Inc. All Tights reserved.
作者：
Malyshev, D. S.Natl Res Univ
Higher Sch Econ 25-12 Bolshaya Pecherskaya Ulitsa Nizhnii Novgorod 603155 Russia
We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices. (C) 2015 Elsevier B.V. All rights reserved.
We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices. (C) 2015 Elsevier B.V. All rights reserved.
The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph cl...
详细信息
The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for H-free graphs if H is not a linear forest. On the other hand, the problem is known to be polynomial-time solvable for sP(2)-free graphs for any integer s >= 1. We give a polynomial-time algorithm to solve the problem for (sP(1)+P-5)-free graphs for every integer s >= 0. Our algorithm can also be used for the WEIGHTED CONNECTED VERTEX COVER problem.
Efficient inspection of ships at ports to ensure their compliance with safety and environmental regulations is of vital significance to maritime transportation. Given that maritime authorities often have limited inspe...
详细信息
Efficient inspection of ships at ports to ensure their compliance with safety and environmental regulations is of vital significance to maritime transportation. Given that maritime authorities often have limited inspection resources, we proposed three two-step approaches that match the inspection resources with the ships, aimed at identifying the most deficiencies (non-compliances with regulations) of the ships. The first approach predicts the number of deficiencies in each deficiency category for each ship and then develops an integer optimization model that assigns the inspectors to the ships to be inspected. The second approach predicts the number of deficiencies each inspector can identify for each ship and then applies an integer optimization model to assign the inspectors to the ships to be inspected. The third approach is a semi-"smart predict then optimize" (semi-SPO) method. It also predicts the number of deficiencies each inspector can identify for each ship and uses the same integer optimization model as the second approach, however, instead of minimizing the mean squared error as in the second approach, it adopts a loss function motivated by the structure of the optimization problem in the second approach. Numerical experiments show that the proposed approaches improve the current inspection efficiency by over 4% regarding the total number of detected deficiencies. Through comprehensive sensitivity analysis, several managerial insights are generated and the robustness of the proposed approaches is validated. (c) 2020 Elsevier Ltd. All rights reserved.
Response function (RF), which gives the value of maximum feasible outputs in response to changing the inputs, has a crucial role in performance analysis and scale elasticity measurement. In this paper, a polynomial-ti...
详细信息
Response function (RF), which gives the value of maximum feasible outputs in response to changing the inputs, has a crucial role in performance analysis and scale elasticity measurement. In this paper, a polynomial-time algorithm is provided which is able to obtain the closed form of the RF under (nonconvex) FDH productions technologies. Finite convergence of the presented algorithm is proved;and it is established that the algorithm is polynomial-time from a complexity standpoint. Moreover, an application of the proposed procedure with real-world data accompanying some experiment-based computational discussions are given.
暂无评论